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 The function rand(a..b)()
gives a random integer between and Combining these, we can find a prime:
> nextprime(rand(..)())
73050570031667109175215303340488313456708913284291
If we repeat this procedure, we should get another prime:
> nextprime(rand(..)())
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 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 and
SOLUTION
First, change the message to numbers:
> text2num("hi")
809
Now, raise it to the th power mod
> %&17 mod 823091
596912
You might need a before the 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 To do this, we need to find One way is
> phi(823091)
821184
Another way is to factor as and then compute
> ifactor(823091)
(659)(1249)
> 658*1248
821184
Since we compute the following (note that we are finding the inverse of mod not mod ):
> 17& (-1) mod 821184
48305
Therefore, To decrypt, raise the ciphertext to the th power mod
> 596912&48305 mod 823091
809
Finally, change back to letters:
> num2text(809)
"hi"
Encrypt hellohowareyou
using RSA with and
SOLUTION
First, change the plaintext to numbers:
> text2num("hellohowareyou")
805121215081523011805251521
Suppose we simply raised this to the th power mod
> %&17 mod 823091
447613
If we decrypt (we know from Example 25), we obtain
> %&48305 mod 823091
628883
This is not the original plaintext. The reason is that the plaintext is larger than so we have obtained the plaintext mod
> 805121215081523011805251521 mod 823091
628883
We need to break the plaintext into blocks, each less than In our case, we use three letters at a time:
> 80512&17 mod 823091
757396
> 121508&17 mod 823091
164513
> 152301&17 mod 823091
121217
> 180525&17 mod 823091
594220
> 1521&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&48305 mod 823091
80512
> 164513&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")&rsae mod rsan
709467584676126685983701649915507861828763310606852354105647041144
86782261716497200122155332348462014053287987580899263765142534
> text2num("ba")&rsae mod rsan
350451306089751003250117094498719542737882047539485930603136976982
27621759806027962270538031565564773352033671782261305796158951
> text2num("bar")&rsae mod rsan
448145128638551010760045308594921093424295316066074090703605434080
00843645986880405953102818312822586362580298784441151922606424
> text2num("bard")&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 find the decryption exponent for the RSA Challenge, and decrypt the ciphertext (see Section 9.5).
First we find the decryption exponent:
> rsad:=rsae&(-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&rsad mod rsan)
"the magic words are squeamish ossifrage"
Encrypt the message rsaencryptsmessageswell
using rsan and rsae.
> text2num("rsaencryptsmessageswell")&rsae mod rsan
946394203490022593163058235392494964146409699340017097214043524182
71950654254365584906013966328817753539283112653197553130781884
Decrypt the preceding ciphertext.
SOLUTION
Fortunately, we know the decryption exponent rsad. Therefore, we compute
> %& 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)&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 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
> solve(2 -
(11313771275590312567 - 11313771187608744400 + 1)*x +
11313771275590312567, x)
87852787151, 128781017
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 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 Now choose a random integer Hoping to be lucky, we choose 13. As in the factorization method, we compute
> 13&% mod rsan
275743685070065305922434948688471611984230957073078056905698396470
30183109839862370800529338092984795490192643587960859870551239
Since this is not we successively square it until we get
> %&2 mod rsan
483189603219285155801384764187230345541040990699408462254947027766
54996412582955636035266156108686431194298574075854037512277292
> %&2 mod rsan
781728141548773565791419280587540000219487870564838209179306251152
15181839742056013275521913487560944732073516487722273875579363
> %&2 mod rsan
428361912025087287421992990405829002029762229160177671675518702165
09444518239462186379470569442055101392992293082259601738228702
> %&2 mod rsan
1
Since the last number before the 1 was not we have an example of with Therefore, 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 by the method.
SOLUTION
Let’s choose our bound as and let’s take so we compute
> 2&factorial(100)
mod 376875575426394855599989992897873239
369676678301956331939422106251199512
Then we compute the gcd of and
> gcd(% - 1, 376875575426394855599989992897873239)
430553161739796481
This is a factor The other factor is
> 376875575426394855599989992897873239/%
875328783798732119
Let’s see why this worked. The factorizations of and are
> ifactor(430553161739796481 - 1)
(2)(3)(5)(7)(11)(47)
> ifactor(875328783798732119 - 1)
(2)(61)(8967967)(20357)(39301)
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