Two functions, nextprime and randprime, can be used to generate prime numbers. The function nextprime takes a number $n$ as input and attempts to find the next prime after $n$. The function randprime takes a number $n$ as input and attempts to find a random prime between $1$ and $n$. It uses the Miller-Rabin test described in Chapter 9.

>> nextprime(346735)

ans =
   346739

>> randprime(888888)

ans =
   737309

For larger inputs, use symbolic mode:

>> nextprime(10^sym(60))

ans =
   1000000000000000000000000000000000000000000000000000000000007

>> randprime(10^sym(50))

ans =
   58232516535825662451486550708068534731864929199219

It is interesting to note the difference that the ’ ’ makes when entering a large integer:

>> nextprime(sym(’123456789012345678901234567890’))

ans =
   123456789012345678901234567907

>> nextprime(sym(123456789012345678901234567890))

ans =
   123456789012345677877719597071

In the second case, the input was a number, so only the first 16 digits of the input were used correctly when changing to symbolic mode, while the first case regarded the entire input as a string and therefore used all of the digits.

Suppose you want to change the text hellohowareyou to numbers:

>> text2int1(’hellohowareyou’)

ans =
   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$. Note that this uses fewer digits.)

Now suppose you want to change it back to letters:

>> int2text1(805121215081523011805251521)

ans =
   ’hellohowareyou’

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

SOLUTION

First, change the message to numbers:

>> text2int1(’hi’)

ans =
   809

Now, raise it to the $e$th power mod $n$:

>> powermod(ans,17,823091)

ans =
   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

>> eulerphi(823091)

ans =
   821184

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

>> factor(823091)

ans =
    659   1249

>> 658*1248

ans =
   821184

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

>> invmodn(17,821184)

ans =
   48305

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

>> powermod(596912,48305,823091)

ans =
   809

Finally, change back to letters:

>> int2text1(ans)

ans =
   hi

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

SOLUTION

First, change the plaintext to numbers:

>> text2int1(’hellohowareyou’)

ans =
   805121215081523011805251521

Suppose we simply raised this to the $e$th power mod $n$:

>> powermod(ans,17,823091)

ans =
   447613

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

>> powermod(ans,48305,823091)

ans =
   628883

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

>> mod(text2int1(’hellohowareyou’),823091)

ans =
   628883

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

>> powermod(80512,17,823091)

ans =
   757396

>> powermod(121508,17,823091)

ans =
   164513

>> powermod(152301,17,823091)

ans =
   121217

>> powermod(180525,17,823091)

ans =
   594220

>> powermod(1521,17,823091)

ans =
   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:

>> powermod(757396,48305,823091)

ans =
   80512

>> powermod(164513,48305,823091)

ans =
   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

ans =
   114381625757888867669235779976146612010218296721242362562561842935 706935245733897830597123563958705058989075147599290026879543541

>> rsae

ans =
   9007

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

>> powermod(text2int1(’b’), rsae, rsan)

ans =
   709467584676126685983701649915507861828763310606852354105647041144 86782261716497200122155332348462014053287987580899263765142534

>> powermod(text2int1(’ba’), rsae, rsan)

ans =
   350451306089751003250117094498719542737882047539485930603136976982 27621759806027962270538031565564773352033671782261305796158951

>> powermod(txt2int1(’bar’), rsae, rsan)

ans =
   448145128638551010760045308594921093424295316066074090703605434080 00843645986880405953102818312822586362580298784441151922606424

>> powermod(text2int1(’bard’), rsae, rsan)

ans =
   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:

>> rsad=invmodn(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:

>> int2text1(powermod(rsaci, rsad, rsan))

ans =
   the magic words are squeamish ossifrage

Encrypt the message rsaencryptsmessageswell using rsan and rsae.

>> ci = powermod(text2int1(’rsaencryptsmessageswell’), rsae, rsan)
   ci =
   946394203490022593163058235392494964146409699340017097214043524182 71950654254365584906013966328817753539283112653197553130781884

We called the ciphertext ci because we need it in Example 30.

Decrypt the preceding ciphertext.

SOLUTION

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

>> powermod(ans, rsad, rsan)

ans =
   1819010514031825162019130519190107051923051212

>> int2text1(ans)

ans =
   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): ‘ >> powermod((ci - 4)/10, rsad, rsan)

ans =
   4795299917319598866490235262952548640911363389437562984685490797 0588412300373487969657794254117158956921267912628461494475682806

If we try to change this to letters, we get a weird-looking answer. 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 (vpa is for variable precision arithmetic)

>> digits(50); syms y; vpasolve(y^2-(sym(’11313771275590312567’) -sym(’11313771187608744400’)+1)*y+sym(’11313771275590312567’),y)

ans =
   128781017.0 87852787151.0

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*rsad - 1

ans =
   9610344196177822661569190233595838341098541290518783302506446040 41155985575087352659156174898557342995131594680431086921245830097664

>> ans/2

ans =
   4805172098088911330784595116797919170549270645259391651253223020 20577992787543676329578087449278671497565797340215543460622915048832

>> ans/2

ans =
   2402586049044455665392297558398959585274635322629695825626611510 10288996393771838164789043724639335748782898670107771730311457524416

We continue this way for six more steps until we get

ans =
   3754040701631961977175464934998374351991617691608899727541580484 535765568652684971324828808197489621074732791720433933286116523819

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

>>b0=powermod(13, ans, rsan)

b0 =
   2757436850700653059224349486884716119842309570730780569056983964 7030183109839862370800529338092984795490192643587960859870551239

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

>> b1=powermod(b0,2,rsan)

b1 =
   4831896032192851558013847641872303455410409906994084622549470277 6654996412582955636035266156108686431194298574075854037512277292

>> b2=powermod(b1,2,rsan)

b2 =
   7817281415487735657914192805875400002194878705648382091793062511 5215181839742056013275521913487560944732073516487722273875579363

>> b3=powermod(b2, 2, rsan)

b3 =
   4283619120250872874219929904058290020297622291601776716755187021 6509444518239462186379470569442055101392992293082259601738228702

>> b4=powermod(b3, 2, rsan)

b4 =
   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(\text{mod }rsan)$ with $x^2\equiv 1$. Therefore, $\gcd (x-1\text{,}rsan)$ is a nontrivial factor of rsan:

>> gcd(b3 - 1, rsan)

ans =
   32769132993266709549961988190834461413177642967992942539798288533

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

>> rsan/ans

ans =
   3490529510847650949147849619903898133417764638493387843990820577

This is rsap.

Suppose you know that

Factor 205611444308117.

SOLUTION

We use the Basic Principle of Section 9.4.

>> g= gcd(150883475569451-16887570532858,205611444308117)

g =
   23495881

This gives one factor. The other is

>> 205611444308117/g

ans =
   8750957

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

>> primetest(ans)

ans =
   1

>> primetest(g)

ans =
   1

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)$:

>> powermod(2,factorial(100),sym(’37687557542639485559998999 2897873239’)

ans =
   369676678301956331939422106251199512

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

>> gcd(ans - 1, sym’(376875575426394855599989992897873239’)

ans =
   430553161739796481

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

>> sym(’376875575426394855599989992897873239’)/ans

ans =
   875328783798732119

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

>> factor(sym(’430553161739796481’) - 1)

ans =
   [ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 5, 7, 7, 7, 7, 11, 11, 11, 47]

>> factor(sym(’875328783798732119’) - 1)

ans =
   [ 2, 61, 20357, 39301, 8967967]

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