Two functions, nextprime and randprime, can be used to generate prime numbers. The function nextprime takes a number as input and attempts to find the next prime after . The function randprime takes a number as input and attempts to find a random prime between and . 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 . 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 and .
SOLUTION
First, change the message to numbers:
>> text2int1(’hi’)
ans =
809
Now, raise it to the th power mod :
>> powermod(ans,17,823091)
ans =
596912
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
>> eulerphi(823091)
ans =
821184
Another way is to factor as and then compute :
>> factor(823091)
ans =
659 1249
>> 658*1248
ans =
821184
Since , we compute the following (note that we are finding the inverse of mod , not mod ):
>> invmodn(17,821184)
ans =
48305
Therefore, . To decrypt, raise the ciphertext to the th power mod :
>> powermod(596912,48305,823091)
ans =
809
Finally, change back to letters:
>> int2text1(ans)
ans =
hi
Encrypt hellohowareyou
using RSA with and .
SOLUTION
First, change the plaintext to numbers:
>> text2int1(’hellohowareyou’)
ans =
805121215081523011805251521
Suppose we simply raised this to the th power mod :
>> powermod(ans,17,823091)
ans =
447613
If we decrypt (we know 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 , so we have obtained the plaintext mod :
>> mod(text2int1(’hellohowareyou’),823091)
ans =
628883
We need to break the plaintext into blocks, each less than . 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 , 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 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 (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, . 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 factorization method from Section 9.4. First write with 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 . Now choose a random integer . Hoping to be lucky, we choose 13. As in the factorization method, we compute
>>b0=powermod(13, ans, rsan)
b0 =
2757436850700653059224349486884716119842309570730780569056983964 7030183109839862370800529338092984795490192643587960859870551239
Since this is not , we successively square it until we get :
>> 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 , we have an example of with . Therefore, 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 by the method.
SOLUTION
Let’s choose our bound as , and let’s take , so we compute :
>> powermod(2,factorial(100),sym(’37687557542639485559998999 2897873239’)
ans =
369676678301956331939422106251199512
Then we compute the gcd of and :
>> gcd(ans - 1, sym’(376875575426394855599989992897873239’)
ans =
430553161739796481
This is a factor . The other factor is
>> sym(’376875575426394855599989992897873239’)/ans
ans =
875328783798732119
Let’s see why this worked. The factorizations of and 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 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 .