`> `
**divisors(17); # 17 is a prime number:**

`> `
**divisors(15); # 15 isn't a prime number:**

`> `
**divisors(123454321);**

`> `
**divisors(2^13 - 1);**

`> `
**divisors(2^23 + 1);**

__Here are the first 200 primes__
**:**

`> `
**seq(ithprime(k), k=1..200);**

__Here is the 1000-th. prime number__
**:**

`> `
**ithprime(1000);**

__Here is the next prime after the number 20__
**:**

`> `
**nextprime(20);**

**and here - **
__much more spectacularly__
** - is the next prime after the (randomly-typed) number 9998777553210032992874366465554431:**

`> `
**nextprime(9998777553210032992874366465554431);**

__Remark__
**. There is a lot of serious Mathematics going on behind the scenes in making that extremely fast computation ... !!!**

__Returning to RSA cryptography:__

**The (**
**n**
**, **
**e**
**) pair form the ' **
__public-key__
** **
**' (the public paint, as it were) and **

**d**
** is the ' **
__private-key__
** ' (the private paint, as it were)**

**I will create **
__public and private keys__
** for myself (John = **
**j**
**), and will use:**

** **

**pj**
** and **
**qj**
** to denote **
__my two chosen primes__

**nj**
** - my '**
__public modulus__
**' - the product of **
**pj**
** and **
**qj**

**ej**
** to denote **
__my __
__public encryption power__

**dj**
** to denote **
__my __
__private decryption power__

__First my two __
__secret __
__primes__
** (to keep matters **
__simple__
** I am **
__not__
** exercising **
__care__
** with respect to their choice):**

`> `
**pj := nextprime(10^49 + 654321); # 50 digit prime**

`> `
**qj := nextprime(10^69 + 654321654321); # 70 digit prime**

__Next, my public modulus__
**:**

`> `
**nj := pj*qj; # the product of my secretly chosen primes**

__Next, to choose my public encryption power ' __
__ej__
__ '.__

**Recall from earlier that this **
**ej**
** **
__must be chosen__
** so as to satisfy the **
__requirement__
** that **
**ej**
** and (**
**pj**
** - 1) times (**
**qj**
** - 1) are not both divisible by some common whole number greater than 1.**

**Anyone familiar with the mathematics at stake here would know that one has a very high chance of a successful choice if one chooses **
**ej**
** to be a reasonably-sized, randomly-chosen prime.**

__I make an attempt with__
**:**

`> `
**ej := nextprime(1234321); **

__Now I need to test that it satisfies the above requirement.__
** That requires two steps:**

__First__
** I need to calculate the Euler **
**phi-value**
** of my **
**nj**
**:**

`> `
**phi_nj := (pj - 1)*(qj - 1);**

`> `

__Second__
** I must test to see that there is no whole number greater than 1 that divides both **
**ej**
** and **
**phi_nj**
**. That is achieved by using a **
__remarkable idea__
** - known as the**
** Euclidean algorithm**
** - that has come down to us from the renowned 3rd. century B.C. Greek mathematician, **
__Euclid__
**.**

**The mathematics is **
__hidden__
** behind the following:**

`> `
**igcd(ej, phi_nj);**

__A brief mathematical note__
**. That '1' tells us that 1 **
__is__
** the 'greatest common divisor' of **
**ej**
** and **
**phi_nj**
**, and so there is no whole number greater than 1 which divides both **
**ej**
** and **
**phi_nj**
**. **

__Here are a few smaller illustrative examples__
**:**

`> `
**igcd(18, 14);**

`> `
**igcd(15, 21);**

`> `
**igcd(35, 27);**

**Next, to choose my private decryption power '**
__ dj __
__'__
**.**

Recall that that
__requires__
** that **
**dj**
** have the **
__property__
** that the product of **
**ej**
** and **
**dj**
** be a multiple of **
**phi_nj**
**, plus 1.**

**The computation of **
**dj**
** is done by using a remarkable consequence of the Euclidean algorithm - namely the **
**extended Euclidean Algorithm**
**.**

__The mathematics is hidden behind the following __
__two calculations__
__:__

`> `
**igcdex(ej, phi_nj, xj, yj);**

`> `
**dj := xj mod phi_nj; **

**Thus, my **
__private__
** decryption power is the (enormous) number 828349 ... ... ... 181697.**

**It is something of a **
**needle in a haystack**
**!!!**

**In fact, it is the **
__only__
** number between 1 and **
**phi_nj**
** with the **
__required property__
**.**

__Making my public keys known (to the world at large)__
**, I am now set up to **
__receive__
** messages from anyone who knows my public keys, and also to **
__send__
** messages messages to anyone who knows my public keys. **

__For example__
**, let's say that you (Mary) wished to send me this message, **
__using my public keys__
** (it being understood, of course, that we are also using the agreed 'crypt/alphabet'): **
**Meet at cinema, 9.30 P.M. Mary**

__You - Mary - would do this__
**:**

__First__
** convert your message into numerical form, using the to_number procedure:**

`> `
**num1 := to_number(`Meet at cinema, 9.30 P.M. Mary`);**

__Next__
** you perform a **
__single encryption__
** [you are laying one coat of paint] using my **
__public__
** encryption power **
**ej**
**, and my **
__public__
** modulus **
**nj**
**.**

**That involves:**

**raising the number ' **
**num1**
** ' to the power of the number **
**ej**
**, and then **

**calculating the remainder on division by **
**nj**

**That is an **
**extraordinary computational feat**
**, and it exploits a fundamental mathematical construct known as **
**modular exponentiation**
**, using the **
**square-and-multiply **
**technique.**

__The mathematics is hidden in the following - incredibly fast - calculation__
**:**

`> `
**enc1 := num1&^ej mod nj;**

__You send me that number__
** - enc1 - the encrypted form of the (ordinary) numerical form of the message, and then I proceed to decrypt that by using my **
__private__
** decryption power **
**dj.**

**That also entails a modular exponentiation computation [it is actually the application of the private coat of paint], whereby the original numerical form of the text is **
__recovered__
** by raising the numerical form of the encrypted text to the power of the decryption power **
**dj**
**, and calculating the remainder on division by **
**nj:**

`> `
**dec1 := enc1&^dj mod nj;**

__Then I recover the original message by__
**:**

`> `
**text1 := from_number(dec1);**

**Horrah!! All **
__SEEMS__
** fine. You have sent me an encrypted message, and I have decrypted it.**

**But **
__why__
** '**
**seems**
**'? [This brings us to the **
__crux__
** of the matter.] **

**Well, you have used my public key to send me that message, **
__BUT__
** **
__anyone__
** **
__could__
** have sent me that message. **

__Anyone, that is, who knows my public key__
**. **

**'**
__You__
**' **
__could be someone else__
** ... .**

**[I'm not finished yet with the points I wish to make ... .]**

**Equally I could send you a message. **

**I could do it by using **
__your public key__
** (if you had one which I knew), **
__BUT__
** 'I' also could be someone else ... . **

**[I'm still not finished with the points I wish to make ... .]**

**I **
__could__
** send you a message using my own **
__private__
** key (**
__assuming__
** you know my public key), and I could do that **
__NOT__
** by encrypting using my public encryption power (which anyway would require that you knew my private decryption power), **
__BUT__
** by encrypting using my own **
__private__
** decryption power to encrypt. **

__For example__
**, suppose I want to send you (Mary) the message: **
**Can't make it. Too much work. John**

**[My wife would confirm that this is all too realistic an example.]**

**First I convert my message into numerical form, using the to_number procedure:**

`> `
**num2 := to_number(`Can't make it. Too much work. John`);**

__Next__
** I perform a **
__single encryption__
**, **
__BUT__
** using my **
__private__
** decryption power dj, and my **
**public**
** modulus **
**nj:**

`> `
**enc2 := num2&^dj mod nj; **

**I send you that number - enc2 - the encrypted form of the (ordinary) numerical form of the message, and then **
__you__
** then proceed to decrypt that by using my **
__public__
** encryption power **
**ej**
** [the paints have interchangeable properties]:**

`> `
**dec2 := enc2&^ej mod nj;**

**and then you just recover the original message by:**

`> `
**text2 := from_number(dec2);**

**Horrah!! Once again, all **
__SEEMS__
** fine. But why '**
**seems**
**'? **

**Well, at least you **
__know__
** the message has come from me (since - in theory - ONLY I know MY private key), BUT ANYONE could also read that message. **
__Anyone__
**, that is, **
__who__
** (like you) **
__knows my public key__
**.**

__Of course__
**, **
__if__
** you had your public and private keys **
__then__
** that problem could be avoided by my sending you the above message using your public encryption power ... .**

__BUT__
** then you couldn't be sure the message is from me ... .**

**[I hope you see what the problems are ... .]**

**While we are at it - and before showing how all is resolved - I would like to divert briefly to illustrate what happens if someone ATTEMPTS to GUESS my private decryption power, in an attempt to FORGE my signature:**

**Suppose they wished to send the same message as above, and went through the usual steps:**

`> `
**NUM2 := to_number(`Can't make it. Too much work. John`);**

**Let's say they choose the following **
__forged__
** value for my **
__private__
** decryption power [such an attempt is, of course, **
__doomed__
**. They are trying to find that needle in that haystack!!]:**

`> `
**DJ_guess := 98877676655544333221110093465439876548765432;**

__and now encrypted__
**:**

`> `
**ENC2 := NUM2&^DJ_guess mod nj; **

**They send you that number, and you now proceed to (attempt to) decrypt it, using my **
__genuine__
** **
__public__
** key:**

`> `
**DEC2 := ENC2&^ej mod nj; **

**There is nothing apparently untoward there, but now the game is up when you attempt to recover the original text:**

`> `
**text2 := from_number(DEC2);**

__The forger would have wasted his/her time__
**. The message decrypts as **
**gobbledegook**
**.**

__Section Two__
**. How the RSA method is used to provide a '**
**digital signature**
**.'**

**One of the **
__MAJOR__
** applications of public-key cryptography is that it allows **
__SECURE__
** two-way '**
__signed__
**' communication between two parties who each have their own public and private keys (with, of course, an agreed system for converting text into numerical form). [That is what President Clinton and Mr. Ahern were doing in a very public way, but it is exactly what everyone else is doing all the time ... .]**

**Let us have parties A and B with public and private keys (**
**ea**
**, **
**na**
**, **
**da**
**) and (**
**eb**
**, **
**nb**
**, **
**db**
**); then these parties can communicate securely with each other.**

**Implicit in all of this - of course - is the assumption that **
**na**
** and **
**nb**
** have been created so that they **
__cannot__
** be factored quickly!!. That will be discussed in final section, Section Three.**

__This is how it is done__
**:**

__First__
** let's create public and private keys for A and B [I am not going to be fussy about the choice of primes. I am merely choosing them to be 'big']:**

**I make up the first prime, **
**pa**
**, so that it has 100 digits. Because that can take as much as two minutes to compute [depending on the speed of the computer being used] then to save time in my lecture I have privately calculated it, copied and pasted its value into a new region, and simply that **

**can take a while, depending on the speed of the computer]:**

`> `
**# pa := nextprime(10^99 + 8765432109876543211234567834567);**

**Calculated, copied, pasted, and reexecuted (**
__to save time in lecture__
**):**

`> `
**pa := 1000000000000000000000000000000000000000000000000000000000000000000008765432109876543211234567835109;**

__And now for the second prime__
**:**

`> `
**# qa := nextprime(10^119 + 8765432109876543211234567834567);**

**As with **
**pa**
** this has been calculated, copied, pasted, reexecuted **
__to save time__
**:**

`> `
**qa := 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000008765432109876543211234567835227;**

__Now to form A's public modulus__
**:**

`> `
**na := pa*qa;**

__Now to choose A's public encryption power__
**, **
__followed by the other standard computations__
**:**

`> `
**ea := nextprime(12321);**

`> `
**phi_na := (pa - 1)*(qa - 1);**

`> `
**igcdex(ea, phi_na, xa, ya);**

`> `
**da := xa mod phi_na;**

__Now to do make similar choices and calculations for B__
** (once again I have saved lecture time by calculating the two primes, copied, pasted, reexecuted):**

`> `
**# pb := nextprime(10^109 + 2228765432109876543211234567834000); # 110 digits**

`> `
**pb := 10000000000000000000000000000000000000000000000000000000000000000000000000002228765432109876543211234567834173;**

`> `
**# qb := nextprime(10^129 + 2228765432109876543211234567834000); # 130 digits**

`> `
**qb := 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002228765432109876543211234567834077;**

`> `
**nb := pb*qb;**

`> `
**eb := nextprime(54321);**

`> `
**phi_nb := (pb - 1)*(qb - 1);**

`> `
**igcdex(eb, phi_nb, xb, yb);**

`> `
**db := xb mod phi_nb;**

__So, A and B have public and private keys__
**, **
**and we are now in business**
**.**

**Let B send the following message, in signed form to A:**

** **
**If we give you �1,000,000 will we **

get the government contract?

__For technical mathematical reasons__
** - that can only be understood by someone who has really studied the **
**mathematics**
** of all of this - **
__one must KEEP IN MIND__
** that since A's public modulus is **
__LESS__
** than B's (**
**na**
** is less than **
**nb**
**), then one must use the **
__SMALLER__
** modulus **
__FIRST__
** [this just really means that the order in which the paints are applied is important]:**

**The steps are:**

`> `
**B_num := to_number(`If we give you �1,000,000 will we get the government contract?`); **

`> `
**length(B_num);**

**Because B_num is less than **
**na**
**, then the message can be sent as a **
__single block__
** (had that not been so, then one would have had to break up the numerical form of the message into blocks of digits, each having numerical value less than **
**na**
**)**

__B now does a __
__double encryption__
**:**

**FIRST using A's smaller modulus, with A's PUBLIC encryption power [so, laying on A's public paint],**

**SECOND using B's own modulus, with B's PRIVATE decryption power [laying on B's own private paint]:**

`> `
**B_first := B_num&^ea mod na; # SMALLER modulus FIRST**

`> `
**B_second := B_first&^db mod nb;**

**B_second**
** is what A receives, and A now proceeds to do the **
__double decryption__
** as follows (simply **
__reversing__
** the last two steps):**

**FIRST using B's modulus, with B's PUBLIC encryption power [laying on B's public paint], **

**SECOND using A's own modulus, with A's PRIVATE decryption power [laying on A's own private paint]:**

`> `
**A_first := B_second&^eb mod nb;**

`> `
**A_second := A_first&^da mod na;**

`> `
**from_number(A_second);**

__Now let A reply with the message__
**: **

**You're joking! �2,000,000 and it's yours. You'll recoup all with contract. **

Leave cash usual place.

`> `
**A_num := to_number(`You're joking! �2,000,000 and it's yours.You'll recoup all with contract. Leave cash usual place.`);**

`> `
**length(A_num);**

`> `
**length(na);**

**Again, because **
**A_num**
** is less than **
**na**
**, then the message can be sent as a **
__single block__
**.**

`> `
**A_first := A_num&^da mod na; # SMALLER modulus first**

`> `
**A_second := A_first&^eb mod nb;**

`> `

**A_second is what B receives, and B now proceeds to decrypt A's message as follows (simply reversing the last two steps):**

`> `
**B_first := A_second&^db mod nb;**

`> `
**B_second := B_first&^ea mod na;**

`> `
**from_number(B_second);**

__Section Three__
**. The '**
**factorization problem**
**.'**

__A critical observation__
**. **
__You may (indeed, should!) say__
**: **

**"I see how one creates those public and private keys in RSA. One just does the following:**

**1. Choose two primes **
**p**
** and **
**q**
**, and form their product, **
**n**
**.**

**2. Choose an 'encryprion power' **
**e**
** (subject to a certain, minor technical constraint).**

**3. Calculate a 'decryption power' **
**d**
**, **
__in a __
__very__
__ particular way__
**.**

**4. Make (**
**n**
**, e) **
__public__
** **
**but keep **
**d**
** **
__private__
**. **

__Surely__
** that '**
**d**
**' is **
__not really__
** private (in the sense of remaining unknown)?**

__Surely__
** if you knew a person's **
**public**
**-key**
** - their (**
**n**
**, **
**e**
**) pair - you could just perform a certain calculation, and compute the value of their**

**private-key**
** - their **
**d**
** - and on intercepting any messages sent to them proceed to decrypt the message? " [end of quote]**

__I say to you, show me what you mean__
**, and you might proceed as follows:**

**"I know that Maple (say) has a command that '**
**factors**
**' numbers, meaning that it can break any whole number down into its prime constituents. **
__Here are some examples__
**:**

`> `
**ifactor(91); **

**which shows that 91 is the product of the primes 7 and 13**

`> `
**ifactor(637);**

**which shows that 637 is the product of the primes 7, 7 and 13.**

**And consider the following:**

`> `
**ifactor(509429407491696281);**

**which **
__means__
** that 509429407491696281 is the product of the primes **
** and **
**, and so **
__if__
** someone announced their **
__public__
** (**
**n**
**, **
**e**
**) to be (**
**, **
**), then anyone could calculate that person's **
__private__
** **
**d**
**, and thus **
__be able to decrypt that person's messages__
**.**

__One would just do these calculations__
**:**

`> `
**p := 765432713;**

`> `
**q := 665544337;**

`> `
**e := 8779;**

`> `
**igcdex(e, (p-1)*(q-1), x, y);**

`> `
**d := x mod (p-1)*(q-1);**

**And that's all there is to it!! Given the value of **
**n**
**, one simply factors it, thus finding the values of the **
**p**
** and the **
**q**
**, and from that - using the value of **

**(**
**p**
** - 1)*(**
**q**
** - 1) - one calculates the value of the **
**d**
**, and that's it. Decrypt!!" [end of quote.]**

__I would completely agree with you__
**, but would draw your attention now to the **
__crucial point__
**: **
** all of that depended on your being able to recover the values of those two primes **
**p**
** and **
**q**
** **
**from the value of **
**n**
**.**

__Major point__
**.**

__Multiplying__
** big numbers isn't a problem**

**BUT **
__factoring__
** big numbers is!! More precisely,**

factoring certain BIG numbers is a problem

`> `
**9999999999999999999999999999988888888888888888888888777777777777777777777777777777777777776666666666666666666666666665555555555555555555555555444444444444444444443333333333333333*2222222222222222222222111111111111111111111111111111000000000000000000000000055555555555555555555555555333333333333333333333333333333333;**

`> `
**length(9999999999999999999999999999988888888888888888888888777777777777777777777777777777777777776666666666666666666666666665555555555555555555555555444444444444444444443333333333333333);**

`> `
**length(2222222222222222222222111111111111111111111111111111000000000000000000000000055555555555555555555555555333333333333333333333333333333333);**

**There we saw that the product of one 178-digit number and a 136-digit number was calculated almost instantly.**

**Now let us look at a succession of multiplications, and corresponding factorizations:**

`> `
**p1 := nextprime(38899887766);**

`> `
**q1 := nextprime(64466887766);**

`> `
**n1 := p1*q1; length(n1);**

`> `
**ifactor(n1);**

`> `
**p2 := nextprime(738899887766);**

`> `
**q2 := nextprime(638899887766);**

`> `
**n2 := p2*q2; length(n2);**

`> `
**ifactor(n2);**

`> `
**p3 := nextprime(5538899887766);**

`> `
**q3 := nextprime(3138899887766);**

`> `
**n3 := p3*q3; length(n3);**

`> `
**ifactor(n3);**

**I **
__could__
** continue doing those sorts of calculations, each taking a little longer than the previuos one, but I am going to leap forward somewhat to**

**present you with this number - rather a famous one in the literature - **

** **
**the **
**'RSA_129**
**' number**
**:**

`> `
**RSA_129 := 114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541;**

`> `
**length(RSA_129);**

**I am certainly **
__NOT__
** going to attempt to factor it!!**

**It first came to public attention in Martin Gardiner's much read column in the August 1997 issue of the **
**Scientific American**
**. **

**Rivest, Shamir and Adleman (of RSA fame) threw this number out as a challenge to be factored. Given the then state of mathematical knowledge (as far as factoring was concerned) and computer power, they estimated that it would take some 20,000 years to factor it, and thereby decrypt a message which they had encrypted using it as the '**
**n**
**' part of a public modulus.**

**Briefly, a method known as the 'Quadratic Sieve' - introduced in 1981 by the US mathematician Carl Pomerance - together with thousands of**

**computers worldwide (organised by the Dutch mathematician Arjen Lenstra) - factored it by April 1994, and decrypted the RSA-encrypted**

**message (which, incidentally, was: "**
**The magic words are squeamish ossifrage.**
**")**

**Lenstra, and his co-workers found that **
**RSA_129**
** was the product of the two prime numbers (I show them individually, then their produst, and then show their product really is RSA_129):**

`> `
**f1 := 3490529510847650949147849619903898133417764638493387843990820577;**

`> `
**length(f1);**

`> `
**f2 := 32769132993266709549961988190834461413177642967992942539798288533;**

`> `
**length(f2);**

`> `
**f1*f2;**

`> `
**RSA_129 - f1*f2;**

**If I were to foolishly enter the Maple command:**

`> `
**# ifactor(RSA_129);**

**then the timer would stay on for MANY, MANY years ... .**

__Question__
**. So, it it just a matter of mere size?**

__Answer__
**. No. Size is only **
__part__
** of the problem:**

__I am going to create a number__
** - which I will call by the name 'beyond_RSA_129' - which will have these properties:**

**it will be the **
__product__
** of two primes 'P' and 'Q'**

**I will choose P to be f2 (the greater of the two primes whose product is RSA_129)**

**I will choose Q to be greater than P**

**Those choices will automatically make 'beyond_RSA_129' be greater than RSA_129 (hence the name).**

**This is how I will do it:**

`> `
**P := f2;**

**I am choosing 'Q' to be next prime after the prime 'P', and to save computation time in my lecture I do this:**

`> `
**# Q := nextprime(P);**

`> `
**Q := 32769132993266709549961988190834461413177642967992942539798288793;**

`> `
**beyond_RSA_129 := P*Q;**

`> `
**length(beyond_RSA_129);**

**But now I show you that that number can be QUICKLY factored as follows:**

`> `
**Fermat_factor:=proc(n,start,finish) **

local k, s; readlib(issqr):

for k from start to finish do

if issqr(n+k^2) then s:=sqrt(n+k^2);

lprint(n,`factors as the product of`,

s-k,`and`,s+k); RETURN()

fi od end:

`> `
**Fermat_factor(beyond_RSA_129, 0, 300);**