# Example 22

Suppose you need to find a large random prime of 50 digits. Here is one way. The function NextPrime[x] finds the next prime greater than . The function Random[Integer,{a,b}] gives a random integer between  and . Combining these, we can find a prime:

In:= `NextPrime[Random[Integer, {,  }]]`

Out= `73050570031667109175215303340488313456708913284291`

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

In:= `NextPrime[Random[Integer, {,  }]]`

Out= `97476407694931303255724326040586144145341054568331`

# Example 23

Suppose you want to change the text hellohowareyou to numbers:

In:= `txt2num1["hellohowareyou"]`

Out= `805121215081523011805251521`

Note that we are now using , 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 . Note that this uses fewer digits.)

Now suppose you want to change it back to letters:

In:= `num2txt1`

Out= `hellohowareyou`

# Example 24

Encrypt the message hi using RSA with  and .

SOLUTION

First, change the message to numbers:

In:= `txt2num1["hi"]`

Out= `809`

Now, raise it to the :

In:= `PowerMod[%, 17, 823091]`

Out= `596912`

# Example 25

Decrypt the ciphertext in the previous problem.

SOLUTION

First, we need to find the decryption exponent . To do this, we need to find . One way is as follows:

In:= `EulerPhi`

Out= `821184`

Another way is to factor  as  and then compute :

In:= `FactorInteger`

Out= `{ {659, 1 }, {1249, 1 } }`

In:= `658*1248`

Out= `821184`

Since , we compute the following (note that we are finding the inverse of , not ):

In:= `PowerMod[17, -1, 821184]`

Out= `48305`

Therefore, . To decrypt, raise the ciphertext to the :

In:= `PowerMod[596912, 48305, 823091]`

Out= `809`

Finally, change back to letters:

In:= `num2txt1`

Out= `hi`

# Example 26

Encrypt hellohowareyou using RSA with  and .

SOLUTION

First, change the plaintext to numbers:

In:= `txt2num1["hellohowareyou"]`

Out= `805121215081523011805251521`

Suppose we simply raised this to the :

In:= `PowerMod[%, 17, 823091]`

Out= `447613`

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

In:= `PowerMod[%, 48305, 823091]`

Out= `628883`

This is not the original plaintext. The reason is that the plaintext is larger than , so we have obtained the plaintext :

In:= `Mod[805121215081523011805251521, 823091]`

Out= `628883`

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



In:= `PowerMod[80512, 17, 823091]`

Out= `757396`

In:= `PowerMod[121508, 17, 823091]`

Out= `164513`

In:= `PowerMod[152301, 17, 823091]`

Out= `121217`

In:= `PowerMod[180525, 17, 823091]`

Out= `594220`

In:= `PowerMod[1521, 17, 823091]`

Out= `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:

In:= `PowerMod[757396, 48305, 823091]`

Out= `80512`

In:= `PowerMod[164513, 48305, 823091]`

Out= `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:

In:= `rsan`

Out=

``114381625757888867669235779976146612010218296721242362562561842935 706935245733897830597123563958705058989075147599290026879543541``

In:= `rsae`

Out= `9007`

# Example 27

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

In:= `PowerMod[num1["b"], rsae, rsan]`

Out=

``709467584676126685983701649915507861828763310606852354105647041144 86782261716497200122155332348462014053287987580899263765142534``

In:= `PowerMod[txt2num1["ba"], rsae, rsan]`

Out=

``350451306089751003250117094498719542737882047539485930603136976982 27621759806027962270538031565564773352033671782261305796158951``

In:= `PowerMod[txt2num1["bar"], rsae, rsan]`

Out=

``448145128638551010760045308594921093424295316066074090703605434080 00843645986880405953102818312822586362580298784441151922606424``

In:= `PowerMod[txt2num1["bard"], rsae, rsan]`

Out=

``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.

# Example 28

Using the factorization , find the decryption exponent for the RSA Challenge, and decrypt the ciphertext (see Section 9.5).

SOLUTION

First we find the decryption exponent:

In:=`rsad=PowerMod[rsae,-1,(rsap-1)*(rsaq-1)];`

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

In:=`num2txt1[PowerMod[rsaci, rsad, rsan]]`

Out= `the magic words are squeamish ossifrage`

# Example 29

Encrypt the message rsaencryptsmessageswell using rsan and rsae.

In:= `PowerMod[txt2num1["rsaencryptsmessageswell"], rsae, rsan]`

Out=

``946394203490022593163058235392494964146409699340017097214043524182 71950654254365584906013966328817753539283112653197553130781884``

# Example 30

Decrypt the preceding ciphertext.

SOLUTION

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

In:= `PowerMod[%, rsad, rsan]`

Out= `1819010514031825162019130519190107051923051212`

In:= `num2txt1[%]`

Out= `rsaencryptsmessageswell`

Suppose we lose the final 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):

In:= `PowerMod[(%%% - 4)/10, rsad, rsan]`

Out=

``479529991731959886649023526295254864091136338943756298468549079705 88412300373487969657794254117158956921267912628461494475682806``

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

# Example 31

Suppose we are told that  is the product of two primes and that . Factor .

SOLUTION

We know (see Section 9.1) that  and  are the roots of . Therefore, we compute

In:= `Roots[ - (11313771275590312567 - 11313771187608744400 + 1)*X + 11313771275590312567 == 0, X]`

Out= ``

Therefore, . We also could have used the quadratic formula to find the roots.

# Example 32

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

SOLUTION

We use the  factorization method from Section 9.4. First write  with  odd. One way to do this is first to compute , then keep dividing by 2 until we get an odd number:

In:= `rsae*rsad - 1`

Out=

``961034419617782266156919023359583834109854129051878330250644604041 155985575087352659156174898557342995131594680431086921245830097664``

In:= `%/2`

Out=

``480517209808891133078459511679791917054927064525939165125322302020 577992787543676329578087449278671497565797340215543460622915048832``

In:= `%/2`

Out=

``240258604904445566539229755839895958527463532262969582562661151010 288996393771838164789043724639335748782898670107771730311457524416``

We continue this way for six more steps until we get

Out=

``375404070163196197717546493499837435199161769160889972754158048453 5765568652684971324828808197489621074732791720433933286116523819``

This number is . Now choose a random integer . Hoping to be lucky, we choose 13. As in the  factorization method, we compute

In:= `PowerMod[13, %, rsan]`

Out=

``275743685070065305922434948688471611984230957073078056905698396470 30183109839862370800529338092984795490192643587960859870551239``

Since this is not , we successively square it until we get :

In:= `PowerMod[%, 2, rsan]`

Out=

``483189603219285155801384764187230345541040990699408462254947027766 54996412582955636035266156108686431194298574075854037512277292``

In:= `PowerMod[%, 2, rsan]`

Out=

``781728141548773565791419280587540000219487870564838209179306251152 15181839742056013275521913487560944732073516487722273875579363``

In:= `PowerMod[%, 2, rsan]`

Out=

``428361912025087287421992990405829002029762229160177671675518702165 09444518239462186379470569442055101392992293082259601738228702``

In:= `PowerMod[%, 2, rsan]`

Out= `1`

Since the last number before the 1 was not , we have an example of  with . Therefore,  is a nontrivial factor of rsan:

In:= `GCD[%% - 1, rsan]`

Out=

``32769132993266709549961988190834461413177642967992942539798288533``

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

In:= `rsan/%`

Out=

``3490529510847650949147849619903898133417764638493387843990820577``

This is rsap.

# Example 33

Suppose you know that



Factor 205611444308117.

SOLUTION

We use the Basic Principle of Section 9.4.

In:= `GCD[150883475569451-16887570532858,205611444308117]`

Out= `23495881`

This gives one factor. The other is

In:= `205611444308117/%`

Out= `8750957`

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

In:= `PrimeQ[%%]`

Out= `True`

In:= `PrimeQ[%%]`

Out= `True`

# Example 34

Factor  by the  method.

SOLUTION

Let’s choose our bound as , and let’s take , so we compute :

In:= PowerMod[2,Factorial,37687557542639485559998999289787 3239]

Out= `369676678301956331939422106251199512`

Then we compute the gcd of  and :

In:= `GCD[% - 1, 376875575426394855599989992897873239]`

Out= `430553161739796481`

This is a factor . The other factor  is

In:= `376875575426394855599989992897873239/%`

Out= `875328783798732119`

Let’s see why this worked. The factorizations of  and  are

In:= `FactorInteger[430553161739796481 - 1]`

Out= `{{2, 18 }, {3, 7 }, {5, 1 }, {7, 4 }, {11, 3 }, {47, 1 }}`

In:= `FactorInteger[875328783798732119 - 1]`

Out= `{{2, 1 }, {61, 1 }, {20357, 1 }, {39301, 1 }, {8967967, 1 }}`

We see that  is a multiple of , so . However,  is not a multiple of , so it is likely that . Therefore, both  and  have  as a factor, but only  has  as a factor. It follows that the gcd is .