Suppose you need to find a large random prime of 50 digits. Here is one way. The function nextprime finds the next prime greater than $x\text{.}$ The function rand(a..b)() gives a random integer between $a$ and $b\text{.}$ Combining these, we can find a prime:

> nextprime(rand($10^49$..$10^50$)())

         73050570031667109175215303340488313456708913284291

If we repeat this procedure, we should get another prime:

> nextprime(rand($10^49$..$10^50$)())

         97476407694931303255724326040586144145341054568331

Suppose you want to change the text hellohowareyou to numbers:

> text2num("hellohowareyou")

                    805121215081523011805251521

Note that we are now using a = 1, b = 2, ..., z = 26, since otherwise a’s at the beginnings of messages would disappear. (A more efficient procedure would be to work in base 27, so the numerical form of the message would be $8+5\cdot 27+12\cdot {27}^2+\cdots +21\cdot {27}^{13}=87495221502384554951\text{.}$ Note that this uses fewer digits.)

Now suppose you want to change it back to letters:

> num2text(805121215081523011805251521)

                        "hellohowareyou"

Encrypt the message hi using RSA with $n=823091$ and $e=17\text{.}$

SOLUTION

First, change the message to numbers:

> text2num("hi")

                   809

Now, raise it to the $e$th power mod $n\text{:}$

> %&$\stackrel{\mathbf{ˆ}}{\phantom{\mathbf{a}}}$17 mod 823091

                          596912

You might need a $\mathrm{\setminus }$ before the $\hat{\phantom{a}}\text{.}$ Use the right arrow to escape from the exponent mode.

Decrypt the ciphertext in the previous problem.

SOLUTION

First, we need to find the decryption exponent $d\text{.}$ To do this, we need to find $\varphi (823091)\text{.}$ One way is

> phi(823091)

                 821184

Another way is to factor $n$ as $p\cdot q$ and then compute $(p-1)(q-1)\text{:}$

> ifactor(823091)

                   (659)(1249)

> 658*1248

                     821184

Since $de\equiv 1(\text{mod}\varphi (n))\text{,}$ we compute the following (note that we are finding the inverse of $e$ mod $\varphi (n)\text{,}$ not mod $n$):

> 17&$\stackrel{\mathbf{ˆ}}{\phantom{\mathbf{a}}}$ (-1) mod 821184

                            48305

Therefore, $d=48305\text{.}$ To decrypt, raise the ciphertext to the $d$th power mod $n\text{:}$

> 596912&$\stackrel{\mathbf{ˆ}}{\phantom{\mathbf{a}}}$48305 mod 823091
                             809

Finally, change back to letters:

> num2text(809)

                      "hi" 

Encrypt hellohowareyou using RSA with $n=823091$ and $e=17\text{.}$

SOLUTION

First, change the plaintext to numbers:

> text2num("hellohowareyou")

                    805121215081523011805251521

Suppose we simply raised this to the $e$th power mod $n\text{:}$

> %&$\stackrel{\mathbf{ˆ}}{\phantom{\mathbf{a}}}$17 mod 823091

                         447613

If we decrypt (we know $d$ from Example 25), we obtain

> %&$\stackrel{\mathbf{ˆ}}{\phantom{\mathbf{a}}}$48305 mod 823091

                        628883

This is not the original plaintext. The reason is that the plaintext is larger than $n\text{,}$ so we have obtained the plaintext mod $n\text{:}$

> 805121215081523011805251521 mod 823091

                             628883

We need to break the plaintext into blocks, each less than $n\text{.}$ In our case, we use three letters at a time:

> 80512&$\stackrel{\mathbf{ˆ}}{\phantom{\mathbf{a}}}$17 mod 823091

                           757396
                           
> 121508&$\stackrel{\mathbf{ˆ}}{\phantom{\mathbf{a}}}$17 mod 823091

                           164513
                           
> 152301&$\stackrel{\mathbf{ˆ}}{\phantom{\mathbf{a}}}$17 mod 823091

                           121217
                           
> 180525&$\stackrel{\mathbf{ˆ}}{\phantom{\mathbf{a}}}$17 mod 823091

                           594220
                           
> 1521&$\stackrel{\mathbf{ˆ}}{\phantom{\mathbf{a}}}$17 mod 823091

                           442163

The ciphertext is therefore 757396164513121217594220442163. Note that there is no reason to change this back to letters. In fact, it doesn’t correspond to any text with letters.

Decrypt each block individually:

> 757396&$\stackrel{\mathbf{ˆ}}{\phantom{\mathbf{a}}}$48305 mod 823091

                             80512
                             
> 164513&$\stackrel{\mathbf{ˆ}}{\phantom{\mathbf{a}}}$48305 mod 823091

                             121508

etc.

We’ll now do some examples with large numbers, namely the numbers in the RSA Challenge discussed in Section 9.5. These are stored under the names rsan, rsae, rsap, rsaq:

> rsan

114381625757888867669235779976146612010218296721242362562561842935
706935245733897830597123563958705058989075147599290026879543541

> rsae
                         9007

Encrypt each of the messages b, ba, bar, bard using rsan and rsae.

> text2num("b")&$\stackrel{\mathbf{ˆ}}{\phantom{\mathbf{a}}}$rsae mod rsan

709467584676126685983701649915507861828763310606852354105647041144
86782261716497200122155332348462014053287987580899263765142534

> text2num("ba")&$\stackrel{\mathbf{ˆ}}{\phantom{\mathbf{a}}}$rsae mod rsan

350451306089751003250117094498719542737882047539485930603136976982
27621759806027962270538031565564773352033671782261305796158951

> text2num("bar")&$\stackrel{\mathbf{ˆ}}{\phantom{\mathbf{a}}}$rsae mod rsan

448145128638551010760045308594921093424295316066074090703605434080
00843645986880405953102818312822586362580298784441151922606424

> text2num("bard")&$\stackrel{\mathbf{ˆ}}{\phantom{\mathbf{a}}}$rsae mod rsan

242380777851116664232028625120903173934852129590562707831349916142
56054323297179804928958073445752663026449873986877989329909498

Observe that the ciphertexts are all the same length. There seems to be no easy way to determine the length of the corresponding plaintext.

Using the factorization $rsap=rsap\cdot rsap\text{,}$ find the decryption exponent for the RSA Challenge, and decrypt the ciphertext (see Section 9.5).

First we find the decryption exponent:

> rsad:=rsae&$\stackrel{\mathbf{ˆ}}{\phantom{\mathbf{a}}}$(-1) mod (rsap-1)*(rsaq-1):

Note that we use the final colon to avoid printing out the value. If you want to see the value of rsad, see Section 9.5, or don’t use the colon. To decrypt the ciphertext, which is stored as rsaci, and change to letters:

> num2text(rsaci&$\stackrel{\mathbf{ˆ}}{\phantom{\mathbf{a}}}$rsad mod rsan)

           "the magic words are squeamish ossifrage"

Encrypt the message rsaencryptsmessageswell using rsan and rsae.

> text2num("rsaencryptsmessageswell")&$\stackrel{\mathbf{ˆ}}{\phantom{\mathbf{a}}}$rsae mod rsan

946394203490022593163058235392494964146409699340017097214043524182
71950654254365584906013966328817753539283112653197553130781884

Decrypt the preceding ciphertext.

SOLUTION

Fortunately, we know the decryption exponent rsad. Therefore, we compute

> %&$\stackrel{\mathbf{ˆ}}{\phantom{\mathbf{a}}}$ rsad mod rsan

            1819010514031825162019130519190107051923051212

> num2text(%)

                      "rsaencryptsmessageswell"

Suppose we lose the final digit 4 of the ciphertext in transmission. Let’s try to decrypt what’s left (subtracting 4 and dividing by 10 is a mathematical way to remove the 4):

> (%%% - 4)/10)&$\stackrel{\mathbf{ˆ}}{\phantom{\mathbf{a}}}$rsad mod rsan

479529991731959886649023526295254864091136338943756298468549079705
88412300373487969657794254117158956921267912628461494475682806

If we try to change this to letters, we do not get anything resembling the message. A small error in the plaintext completely changes the decrypted message and usually produces garbage.

Suppose we are told that $n=11313771275590312567$ is the product of two primes and that $\varphi (n)=11313771187608744400\text{.}$ Factor $n\text{.}$

SOLUTION

We know (see Section 9.1) that $p$ and $q$ are the roots of $X^2-(n-\varphi (n)+1)X+n\text{.}$ Therefore, we compute

> solve($\mathrm{x}\stackrel{\mathbf{ˆ}}{\phantom{\mathbf{a}}}$2 -
(11313771275590312567 - 11313771187608744400 + 1)*x +
11313771275590312567, x)

                      87852787151, 128781017

Therefore, $n=128781017\cdot 87852787151\text{.}$ We also could have used the quadratic formula to find the roots.

Suppose we know rsae and rsad. Use these to factor rsan.

SOLUTION

We use the $a^r\equiv 1$ factorization method from Section 9.4. First write $rsae\cdot rsad-1=2^{s}m$ with $m$ odd. One way to do this is first to compute $rsae\cdot rsad-1\text{,}$ and then keep dividing by 2 until we get an odd number:

> rsae*rsad - 1

961034419617782266156919023359583834109854129051878330250644604041
155985575087352659156174898557342995131594680431086921245830097664

> %/2

480517209808891133078459511679791917054927064525939165125322302020
577992787543676329578087449278671497565797340215543460622915048832

> %/2
240258604904445566539229755839895958527463532262969582562661151010
288996393771838164789043724639335748782898670107771730311457524416

We continue this way for six more steps until we get

375404070163196197717546493499837435199161769160889972754158048453
5765568652684971324828808197489621074732791720433933286116523819

This number is $m\text{.}$ Now choose a random integer $a\text{.}$ Hoping to be lucky, we choose 13. As in the $a^r\equiv 1$ factorization method, we compute

> 13&$\stackrel{\mathbf{ˆ}}{\phantom{\mathbf{a}}}$% mod rsan

275743685070065305922434948688471611984230957073078056905698396470
30183109839862370800529338092984795490192643587960859870551239

Since this is not $\pm 1(\text{mod}rsan)\text{,}$ we successively square it until we get $\pm 1\text{:}$

> %&$\stackrel{\mathbf{ˆ}}{\phantom{\mathbf{a}}}$2 mod rsan

483189603219285155801384764187230345541040990699408462254947027766
54996412582955636035266156108686431194298574075854037512277292

> %&$\stackrel{\mathbf{ˆ}}{\phantom{\mathbf{a}}}$2 mod rsan

781728141548773565791419280587540000219487870564838209179306251152
15181839742056013275521913487560944732073516487722273875579363

> %&$\stackrel{\mathbf{ˆ}}{\phantom{\mathbf{a}}}$2 mod rsan

428361912025087287421992990405829002029762229160177671675518702165
09444518239462186379470569442055101392992293082259601738228702

> %&$\stackrel{\mathbf{ˆ}}{\phantom{\mathbf{a}}}$2 mod rsan

                          1

Since the last number before the 1 was not $\pm 1(\text{mod}rsan)\text{,}$ we have an example of $x\cancel{\equiv }\pm 1(\text{mod}rsan)$ with $x^2\equiv 1\text{.}$ Therefore, $gcd(x-1\text{,}rsan)$ is a nontrivial factor of rsan:

> gcd(%% - 1, rsan)

32769132993266709549961988190834461413177642967992942539798288533

This is rsaq. The other factor is obtained by computing rsan/rsaq:

rsan/%

3490529510847650949147849619903898133417764638493387843990820577

This is rsap.

Suppose you know that

Factor 205611444308117.

SOLUTION

We use the Basic Principle of Section 9.4:

> gcd(150883475569451-16887570532858,205611444308117)

                            23495881

This gives one factor. The other is

> 205611444308117/%

                     8750957

We can check that these factors are actually primes, so we can’t factor any further:

> isprime(%%)

                   true

> isprime(%%)

                   true

Factor $n=376875575426394855599989992897873239$ by the $p-1$ method.

SOLUTION

Let’s choose our bound as $B=100\text{,}$ and let’s take $a=2\text{,}$ so we compute $2^{100!}(\text{mod}n)\text{:}$

> 2&$\stackrel{\mathbf{ˆ}}{\phantom{\mathbf{a}}}$factorial(100)
mod 376875575426394855599989992897873239

               369676678301956331939422106251199512

Then we compute the gcd of $2^{100!}-1$ and $n\text{:}$

> gcd(% - 1, 376875575426394855599989992897873239)

                        430553161739796481

This is a factor $p\text{.}$ The other factor $q$ is

> 376875575426394855599989992897873239/%

                        875328783798732119

Let’s see why this worked. The factorizations of $p-1$ and $q-1$ are

> ifactor(430553161739796481 - 1)

                     (2)${}^{18}$(3)${}^7$(5)(7)${}^4$(11)${}^3$(47)

> ifactor(875328783798732119 - 1)

                  (2)(61)(8967967)(20357)(39301)

We see that $100!$ is a multiple of $p-1\text{,}$ so $2^{100!}\equiv 1(\text{mod}p)\text{.}$ However, $100!$ is not a multiple of $q-1\text{,}$ so it is likely that $2^{100!}\cancel{\equiv }1(\text{mod}q)\text{.}$ Therefore, both $2^{100!}-1$ and $pq$ have $p$ as a factor, but only $pq$ has $q$ as a factor. It follows that the gcd is $p\text{.}$