RSA Coding - by Dr. Sarah - Adapted from Bill Bauldry's Cryptography in the Classroom.

Sophie Germain primes are still of interest today. People are still trying to find larger and larger Sophie Germain primes. These primes are of interest in coding systems.

In 1977, Ronald Rivest, Adi Shamir, and Len Adelman invented a coding system called RSA that is the most successful current commercial cryptosystem. A public key for encoding is given to anyone, while a private key for decoding is kept secret. The security of the system is based on the idea that factoring large numbers is extraordinarily difficult to do in practice.

The coding system is based on modular arithmetic.
a mod b is the whole number remainder of a/b. So, 9 mod 6 = 3, because 3 is the whole number remainder when 9 is divided by 6. You can also do this on your calculator. 9/6=1.5, so we take the decimal part (.5) and multiply by 6 to get back 3.

To Code and Decode

  • We start with 2 primes p and q that have many digits (at least 200 digits each). We could use a Sophie Germain prime to obtain our two prime numbers, because when you have a Sophie Germain prime, you automatically get another prime number, by doubling it and adding one.

  • We find numbers e (encoding number) and d (decoding number) so that e d mod (p-1)(q-1) = 1. There are mathematical methods of finding e and d, but we won't go over them. (Extra credit if you read the relevant section in the Heart of Math book and report back on it).

  • Let n = p q. We publish e and n. To encode a message, words are first converted to a long string of numbers. For example, my initials, SG, might be converted to 1907 via the conversion a-->01, b-->02, ..., z-->26. Then, we take the string of numbers, raise it to the eth power, and reduce mod n. This gives us the coded message. For example,
    1907e mod n
    is the coded message. Notice that anyone can encode since they know e and n, which have been made public.

  • RSA coding is based on the fact that d is kept secret. We decode via taking the coded message, raising it to the dth power, and reducing mod n. For example, if the coded message was 232, the decoded message would be
    232d mod n.
    Notice that you can't decode unless you know d, which is kept secret. In addition, we can't just solve for d, since we would need p and q to do so in order to solve the equation ed mod (p-1)(q-1)=1 for d. But, n has so many digits that it is very hard for a computer to factor n into the product pq at present computer speeds, so people cannot solve for d. Hence, they cannot decode messages.

    • To Review:
    Start with two large primes (could use a Sophie Germain prime p, and 2p+1)
    Now find e and d, the encoding and decoding numbers, by an equation that involves modular arithmetic.
    To encode we turn our message into numbers and then calculate (uncoded message) e mod n.
    To decode we calculate (coded message) d mod n and then turn our numerical message into letters.
    Since d is kept secret and is very hard to solve for, this is a good coding system!

    An Example:

    We'll choose p=163 and q=229 as examples to work with in order to give you a better sense of some of the issues involved. Note that these aren't 200 digits each, as they are only 3 digits long, but that would take way too much space and time to work with here.

    e and d can be found via a mathematical process (that we won't go into) to be e=1151 and d=5327. Let's check that e and d satisfy e d mod (p-1)(q-1) = 1. In other words, we want to check that 1151*5327 mod (163-1)(229-1) = 1. This is equivalent to checking that 1151*5327 mod (162)(228) = 1, which is the same as 6131377 mod 36936. So, we want the remainder when 6131377 is divided by 36936. So, I would take 6131377 and divide by 36936. We get 166.00002707... Since we want the remainder, we subtract 166, and then multiply by 36936. We get an answer of 1 (recall that the calculator has rounded, so that changes the answer slightly). Hence 1151*5327 mod (163-1)(229-1) = 1, and so we see that e and d were valid numbers to use for encoding and decoding.

    In order to encode SG, which was converted to 1907, we look at 1907^e mod n = 1907^1151 mod 163*229= 1907^1151 mod 37327. Try doing this on your calculator. You will get an error. This is because there are too many digits for your calculator. And remember, p and q are supposed to be hundreds of digits long. We took them as only 3 digits long just for convenience.

    1907^1151 =
    48266709878405307661281099630468094947435767416330266037069999229685526399001717228362742719735224186473557228160078042982698545335872414757458291747485513597369361798406749950425920404539013608472851455295280391529251834595409223724175113721800157343233020646232820978812970572493632405115073884616621935536432317522568793482561760590544474601185565795926988232071071242632502919525565149426264672585590854166240676834704693824545805360240217199257960857643387709531379372318810662093251873911911081182843779480640642748639549442305287082967686623676253566150494940451952406299827870872990633294689218179044485579157515539564144133588442203780895066476083957815633278229216196999493283059487624239638042122068962447331134650610281975376955766325391721979130318507158654929152967183699018422181837600516921591125605092916441781172909336658246697653050418637205707945196835905825299178866464602695167496120512320120642116344142727071690078057556127419592379655462803517250794360648577748571095319055843133884453145755990224953987208106184062961704854386391793808322006688617067320928391135745869514140372398856234344824294944609622948134836892608757221004093450813466776020231349133861528315371448275356196717123109588003966284920848623497663458909723338006963262453067743622487282660026948796829707222304627236024551096382378156756288189989898468055654663991732747956778871616398725823194229877229628300009797724230315902381443438423662906965765524613393626054774606938232543791383106515842513199917563648450138711802072409921020719804291556069150557247295585812112927701263518127169663935460011549131908411641078399909869679488537259895009549454336986438370777921632072178765707432409473966961831930099512917004719327933179404431453025169658691375005356672519604329369975982396453790376738333852807275295347527920347427057573343274685084148157341072311309612479162359377101539757804717064317667133717464389572779134637352396054410778868619785335209237380048835235629154229707848127040322934890132661942405180224314185747231869535911463112301525883783713622212636195649028000512167734490333767723213493223611930586309534859604091050234017713579480931854411364933939502207578587791588766345696063992120893894306556490045856924903056761397271320346893607056399030197259999468924718253124210967734944126830716508120670429023952811771969940561946458713807725213782656577982533046525932222566015522891690739666467549603609206270712178707910078252246683649669649404068009847575420796497096812749711498889646998017512620666938651983979561105598949894175299985033911218047384033034936123788312269704134973816112214384135785297756679817158868759207184509768278612866583291242610418108469005393771051924688812987705739855163993558136790629215123530025709348537008970592018672173826995187327087767478021517101472819433985917323020557104725871896532914292167917168410304615056770573147139142871678027328826692487909260199327612306763222637961038294862006013857631095077616886243204741832103244134015770871520783203953695956770782854729747047561731057108871584336812597275044226587467710392940168627804386493865411114823638787801710714680632995117233378796598618640572762037074622863020369774922976479877540329642843201717579448405052851959552799154396022424233015930106585878790484832764745691713716699795674916161727739024919082513189118952409905259870828436854686875755122838320254688057380861000385100463393392427236862123734114631505678352185440949566006494688266278970348461334183686325699422382296238729988227381958348593055124414377452107286171089691089597616969074928345688761946855822004887837582365470973815138621926670172686432355742508300820326076109730443320304240058298362003251128535743727915802065974625173683736920078939249209402112005278777495865123494355414315804326843
    Look how many digits 1907^1151 is - no wonder you couldn't do it on your calculator - 3776 digits!

    Now let's reduce mod 37327 -- 1907^1151 mod 37327 = 12525
    So, 12525 is the coded message standing for SG. No one can decode this message unless they have d.
    To decode, I do (coded message)^d mod n = 12525^5327 mod 37327 and get back 1907, which I then convert back to SG.

    In practice, as mentioned before, we start with prime numbers p and q that are at least 200 digits long. The block size (the length of the string of letters we convert to numbers) is the largest grouping that stays less than n=pq. So, if I have a page of text, I divide it up into blocks that are as large as possible (less than n) and then convert these blocks to numbers. Then, I take those numbers, raise them to the eth power, and reduce mod n. For the numbers used in real life, it would be impossible (with present computer speeds and memory) to directly raise them to the eth power. Instead, the "square and multiply" function for calculating powers with large numbers in modular arithmetic is a clever way to easily calculate modular powers. The basic idea is to square the number, then reduce it mod n (this gives the remainder, which is must smaller than the square), and then multiply again and reduce mod n, and keep repeating this process until we have found the number to the eth power mod n. By reducing mod n every time we square or multiply, the numbers are kept small. You would be surprised to find out how quickly your calculator can "square and multiply" to find that 1907^1151 mod 37327 = 12525, even though it cannot do the 1907^1151 part of the calculation directly.