> 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);

An almost instantaneous factorisation !!

How was that possible? It would not be possible to go into the exact details here in a public lecture, but suffice it to say that it involves little more than

elementary school work (IF I have time I may ... ).

What I will let out however is that the success was whooly dependant on the CRITICAL fact that the two primes P and Q - although large - are relatively close to each other :

> Q - P;

What - though - if one doesn't choose two primes that are relatively close to each other? Suppose one choose them so that they were quite far apart?

That's what I'm now going to do.

This time I will make up another number - I will call it 'way_beyond_RSA_129' - which will have these properties:

it will be the product of two primes 'P1' and 'Q1'

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

I will choose Q1 to be MUCH greater than P1

This is how I will do it:

> P1 := f2;

To save computation time in my lecture I do this:

> # Q1 := nextprime(4470115461512684340891257138125051110076800700282905015819080092370422104067183317016903679999999999999630);

> Q1 := 4470115461512684340891257138125051110076800700282905015819080092370422104067183317016903680000000000000001;

> way_beyond_RSA_129 := P1*Q1;

> length(way_beyond_RSA_129);

> way_beyond_RSA_129 - beyond_RSA_129;

But that MUCH LARGER number can now be QUICKLY factored by doing this:

> Pollard:=proc(n)
local a,k;
a[1]:=2:
for k from 2 while igcd(n,a[k-1]-1 mod n)=1
do a[k]:=a[k-1]&^k mod n od;
lprint(n,`is the PRODUCT of`, igcd(n, a[k-1]-1 mod n), `and`,
n/igcd(n, a[k-1]-1 mod n))
end:

> Pollard(way_beyond_RSA_129);

WONDERFUL!!!

The mathematical ideas behind the success of that factorisation are due to a British mathematician called John Pollard (he lives outside Reading), and were published by him in 1974 in the Mathematical Proceedings of the Cambridge Philosophical Society, in a now famous paper. The method he develops there has become known as 'Pollard's p - 1 method ', and with reason:

In that paper he expounds a very beautiful idea which enables one to factor a number, one of whose prime factors 'p' is such that the number p - 1 has only SMALL prime factors.

That is WHY I was able so quickly to factor the number 'way_beyond_RSA_129. Look at how its prime factor Q1 is structured :

> ifactor(Q1 - 1);

Look at all those SMALL primes: 2, 3, 5, ... , 71 and 73.

I'll let you in on my secret. No, I won't. It would spoil the fun (though some of you may see ... ).

Whereas look at the two prime factors - f1 and f2 - of the RSA_129 number; see how they behave:

> ifactor(f1 - 1);

> ifactor(f2 - 1);

>

Rivest, Shamir and Adleman knew what they were doing in choosing their two primes to make up their 129 digit number.

An attempt at a summary . The current security of the RSA method rests on the general difficulty of factorisation ... .
Besides the Pollard p-1 method there is also his rho- method aka his Monte Carlo method), and there is the Pomerance
quadratic sieve method, Hendrik Lenstra's elliptic curve method, and the current dominant method - the Number Field Sieve method (introduced by Pollard, and added to by many others)

I hope there is enough here for someone who has not been at my public talk to be able to follow this.

Details concerning the Fermat factorisation method, and the Pollard 'p-1' method, may be seen in Maple
worksheets of mine which are available off the Web at the US Naval Academy on David Joyner's:

http://web.usna.navy.mil/~wdj/crypto.htm

When my College has its own Web site [added October 1999: it now does] I will make many more such Maple documents available.

Finally, all of the above, and much, much more besides, is studied by my 3rd. year B.Ed. and B.A. students in their Number Theory and Cryptography course here in St. Patrick's College.

______________________