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 $x$. The function Random[Integer,{a,b}] gives a random integer between $a$ and $b$. Combining these, we can find a prime:

In[1]:= NextPrime[Random[Integer, {$10\hat{\phantom{a}}49$, $10\hat{\phantom{a}}50$ }]]

Out[1]= 73050570031667109175215303340488313456708913284291

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

In[2]:= NextPrime[Random[Integer, {$10\hat{\phantom{a}}49$, $10\hat{\phantom{a}}50$ }]]

Out[2]= 97476407694931303255724326040586144145341054568331

Suppose you want to change the text hellohowareyou to numbers:

In[3]:= txt2num1["hellohowareyou"]

Out[3]= 805121215081523011805251521

Note that we are now using $a=1\text{,}b=2\text{,}\dots \text{,}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+\dots +21\cdot {27}^{13}=87495221502384554951$. Note that this uses fewer digits.)

Now suppose you want to change it back to letters:

In[4]:= num2txt1[805121215081523011805251521]

Out[4]= hellohowareyou

Encrypt the message hi using RSA with $n=823091$ and $e=17$.

SOLUTION

First, change the message to numbers:

In[5]:= txt2num1["hi"]

Out[5]= 809

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

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

Out[6]= 596912

Decrypt the ciphertext in the previous problem.

SOLUTION

First, we need to find the decryption exponent $d$. To do this, we need to find $\varphi (823091)$. One way is as follows:

In[7]:= EulerPhi[823091]

Out[7]= 821184

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

In[8]:= FactorInteger[823091]

Out[8]= { {659, 1 }, {1249, 1 } }

In[9]:= 658*1248

Out[9]= 821184

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

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

Out[10]= 48305

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

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

Out[11]= 809

Finally, change back to letters:

In[12]:= num2txt1[809]

Out[12]= hi

Encrypt hellohowareyou using RSA with $n=823091$ and $e=17$.

SOLUTION

First, change the plaintext to numbers:

In[13]:= txt2num1["hellohowareyou"]

Out[13]= 805121215081523011805251521

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

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

Out[14]= 447613

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

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

Out[15]= 628883

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

In[16]:= Mod[805121215081523011805251521, 823091]

Out[16]= 628883

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

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

Out[17]= 757396

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

Out[18]= 164513

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

Out[19]= 121217

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

Out[20]= 594220

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

Out[21]= 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[22]:= PowerMod[757396, 48305, 823091]

Out[22]= 80512

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

Out[23]= 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[24]:= rsan

Out[24]=

114381625757888867669235779976146612010218296721242362562561842935 706935245733897830597123563958705058989075147599290026879543541

In[25]:= rsae

Out[25]= 9007

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

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

Out[26]=

709467584676126685983701649915507861828763310606852354105647041144 86782261716497200122155332348462014053287987580899263765142534

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

Out[27]=

350451306089751003250117094498719542737882047539485930603136976982 27621759806027962270538031565564773352033671782261305796158951

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

Out[28]=

448145128638551010760045308594921093424295316066074090703605434080 00843645986880405953102818312822586362580298784441151922606424

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

Out[29]=

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 $rsan=rsap\cdot rsaq$, find the decryption exponent for the RSA Challenge, and decrypt the ciphertext (see Section 9.5).

SOLUTION

First we find the decryption exponent:

In[30]:=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[31]:=num2txt1[PowerMod[rsaci, rsad, rsan]]

Out[31]= the magic words are squeamish ossifrage

Encrypt the message rsaencryptsmessageswell using rsan and rsae.

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

Out[32]=

946394203490022593163058235392494964146409699340017097214043524182 71950654254365584906013966328817753539283112653197553130781884

Decrypt the preceding ciphertext.

SOLUTION

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

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

Out[33]= 1819010514031825162019130519190107051923051212

In[34]:= num2txt1[%]

Out[34]= 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[35]:= PowerMod[(%%% - 4)/10, rsad, rsan]

Out[35]=

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.

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

SOLUTION

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

In[36]:= Roots[$\mathrm{X}\widehat{\phantom{\mathrm{a}}}2$ - (11313771275590312567 - 11313771187608744400 + 1)*X + 11313771275590312567 == 0, X]

Out[36]= $\text{X == 128781017 }\left|\right|\text{ X == 87852787151}$

Therefore, $n=128781017\cdot 87852787151$. 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$, then keep dividing by 2 until we get an odd number:

In[37]:= rsae*rsad - 1

Out[37]=

961034419617782266156919023359583834109854129051878330250644604041 155985575087352659156174898557342995131594680431086921245830097664

In[38]:= %/2

Out[38]=

480517209808891133078459511679791917054927064525939165125322302020 577992787543676329578087449278671497565797340215543460622915048832

In[39]:= %/2

Out[39]=

240258604904445566539229755839895958527463532262969582562661151010 288996393771838164789043724639335748782898670107771730311457524416

We continue this way for six more steps until we get

Out[45]=

375404070163196197717546493499837435199161769160889972754158048453 5765568652684971324828808197489621074732791720433933286116523819

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

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

Out[46]=

275743685070065305922434948688471611984230957073078056905698396470 30183109839862370800529338092984795490192643587960859870551239

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

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

Out[47]=

483189603219285155801384764187230345541040990699408462254947027766 54996412582955636035266156108686431194298574075854037512277292

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

Out[48]=

781728141548773565791419280587540000219487870564838209179306251152 15181839742056013275521913487560944732073516487722273875579363

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

Out[49]=

428361912025087287421992990405829002029762229160177671675518702165 09444518239462186379470569442055101392992293082259601738228702

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

Out[50]= 1

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

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

Out[51]=

32769132993266709549961988190834461413177642967992942539798288533

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

In[52]:= rsan/%

Out[52]=

3490529510847650949147849619903898133417764638493387843990820577

This is rsap.

Suppose you know that

Factor 205611444308117.

SOLUTION

We use the Basic Principle of Section 9.4.

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

Out[53]= 23495881

This gives one factor. The other is

In[54]:= 205611444308117/%

Out[54]= 8750957

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

In[55]:= PrimeQ[%%]

Out[55]= True

In[56]:= PrimeQ[%%]

Out[56]= True

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

SOLUTION

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

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

Out[57]= 369676678301956331939422106251199512

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

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

Out[58]= 430553161739796481

This is a factor $p$. The other factor $q$ is

In[59]:= 376875575426394855599989992897873239/%

Out[59]= 875328783798732119

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

In[60]:= FactorInteger[430553161739796481 - 1]

Out[60]= {{2, 18 }, {3, 7 }, {5, 1 }, {7, 4 }, {11, 3 }, {47, 1 }}

In[61]:= FactorInteger[875328783798732119 - 1]

Out[61]= {{2, 1 }, {61, 1 }, {20357, 1 }, {39301, 1 }, {8967967, 1 }}

We see that $100!$ is a multiple of $p-1$, so $2^{100!}\equiv 1(\text{mod}p)$. However, $100!$ is not a multiple of $q-1$, so it is likely that $2^{100!}\cancel{\equiv }1(\text{mod }q)$. 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$.