If this is your first visit, be sure to check out the FAQ by clicking the link above. You may have to register before you can post: click the register link above to proceed.
Conax uses same basic principles to encrypt channels as do other encryption systems.
Basically speaking a encrypted "Control Word" or ECW for short is sent to every card in a message called an Entitlement Control Message or ECM.
A new ECW is sent to every card simultaneously every 5 or 10 seconds or so.
The Card uses the current Operational Key (Key 20, Key21) to decode this ECW into a decoded Control Word or DCW.
The algorithm used to do this decoding of the ECW into DCW is called RSA (a little more about how this works later)
The DCW is then returned by the Smart Card to the CAM, where it is used to decode the incoming video signal. This is done within the CAM using a system called CSA (Common Scrambling Algorithm) to decode the incoming video into a veiwable picture.
From the above we can understand that all cards have the same Operational Key values, because they all have to decode the same ECW to clear a channel. Got that? Good....
Now where do those Operational keys come from and how do they get into the card. Well in the old days they would be preloaded into all the cards when they were manufactured. The problem with this (for the providers, not for us!) is that when hackers opened any one card and got the keys, the only way the provider could stop pirate veiwing would be to replace all the cards. Expensive to do!
So with current systems (like Conax) we have a further step up the ladder.
The Operational keys are sent to all the subscriber cards over the air in a message called an EMM (Entitlement Management Message).
This EMM contains the new Operation Keys to be used next.
Obviously hackers are not allowed to log these new Operation Keys being sent, so again these operational keys in the EMM are encrypted using RSA.
However there is an important difference between EMM and ECM. Where ECM are sent simultaneously to all cards, EMM are sent separately to every card in turn.
An EMM contains an Address of a specific card (known as UA or SA), and an encrypted operational key. The operational key is encrypted in RSA using a Master Key.
This Master Key in conax is key10, and every single card has it's own unique Master Key 10, so a card can only decrypt the EMM addressed specifically to that card.
In other words every EMM contains different encrypted data that can only be decoded by the card it is meant for.
This means that Conax can choose which cards it want's to update with the new key 20 or 21, and which cards it no longer wants to update - like when the subscription expires for example, or a card is reported stolen or lost.
The idea behind all this is that if hackers extract the MK10 from a card, and then publish that key and UA, all Conax needs to do is find the compromised key and address, then stop updating that card and all peoples copies that use the same key.
This is the reason why Master Keys are kept secret amongst small groups of hackers.
What was not considered at the time these systems were invented, is tha tpeople would have such a thing as the internet, where the current Operational keys can be published to many people very quickly, even if the change every day or more often (anyone remember good ol' sexview - 3 updates per day! )
Now a little about RSA itself
This is how it works:
* Find 2 very large primes, p and q.
* Find n=pq (the public modulous).
* Choose e, such that e<n and relatively prime to (p-1)(q-1).
* Compute d=e^-1 mod[(p1-)(q-1)] OR ed=1[mod (p-1)(q-1)].
* e is the public exponent and d is the private one.
* The public-key is (n,e), and the private key is (n,d).
* p and q should never be revealed, preferably destroyed
Encryption is done by dividing the target message into blocks smaller than n and by doing modular exponentiation:
c=m^e mod n
Decryption is simply the inverse operation:
m=c^d mod n
RSA, the first full fledged public key cryptosystem was designed by Rivest, Shamir, and Adleman in 1977.
RSA gets its security from the apparent difficulty in factoring very large composites.
However, nothing has been proven with RSA. It is not proved that factoring the public modulous is the only (best) way to break RSA.
There may be an as yet undiscovered way to break it. It is also not proven that factoring has to be as hard as it is. There exists the possiblity that an advance in number theory may lead to the discovery of a polynomial time factoring algorithm.
But, none of these things has happened, and no current research points in that direction.
However, 3 things that are happening and will continue to happen that take away from the security of RSA are: the advances in factoring technique, computing power and the decrease in the cost of computing hardware.
These things, especially the first one, work against the security of RSA.
However, as computing power increases, so does the ability to generate larger keys.
It is much easier to multiply very large primes than it is to factor the resulting composite (given today's understanding of number theory).
I hope that gives an insight into how these things work. If any of the above doesn't make sense, ask and I will clarify what I can
If you want to study further search the net for links regarding.
RSA
Prime Numbers
Cryptology
Crytanalysis
RSA Attacks
Brute Force Attacks
Timing Attacks
Or just ask here for more info, I'm sure others as well as myself can help you in your studies
iye its alright for those of you that have'nt got an IQ of 2
Thanks dicky. Very interesting read! Funnily enough, network security at uni was my favourite module, although my head is still trying to work out how everything is calculated in RSA encryption. The concept is simple though..
OK let's see if I can explain this a bit more clear than my ramblings above as maybe some did not follow it
To answer direct the questions asked by Hide who started this thread
Right lets see. There are TWO distinct processes going on in Conax (and just about all other encryptions)
1. Process for Decoding the actual picture/sound
-----------------------------------------------
For this the Conax card contains Operational Keys Key20 and 21, but only one of these is used at a time(see below for more about this) - marked (*)
The Process is:
a. CAM sends Encrypted CW to CARD in a message called an ECM
b. CARD uses key 20 or 21 to decode Encrypted CW into Decrypted CW (which is done using the RSA algorithm)
c. Decrypted CW is returned from CARD to CAM
d. CAM uses decrypted CW to decode the video
This process repeats every few seconds when a new ECW is sent to be decoded by the card. Every new ECW (encrypted Control WOrd) arrives in an ECM (Entitlement Control Message) All cards receive the SAME ECM at the SAME time.
If you have a valid key 20 or 21 then you can watch Conax until the key20 or 21 changes - once every day, week, month, whatever they decide it will last for.
2. Process for updating the Operational Keys Key20/21
---------------------------------------------------------------------
a. CAM sends new Encrypted Key 20 or 21 to CARD in a message called an EMM.
b. CARD decrypts the key 20 or 21 using its own UNIQUE master key 10 (to ensure the card decodes the correct EMM they attach a unique address to each EMM so the card knows which EMM to decrypt)
c. The decrypted key 20 or 21 is NOT sent back to the cam. It STAYS IN THE CARD for use in the above process 1.
Every EMM is unique to the card it was meant for.
Every EMM has a different encoded key 20 or 21, EVERY CARD HAS A UNIQUE KEY 10
However when the EMM is decoded with the correct key 10, every card produces the SAME decoded key20 or 21
Like this:
Encrypted Key 20 123456789 + MK10 (card a) = key 20 12AB4356
Encrypted Key 20 342575357 + MK10 (card b) = Key 20 12AB4356
Encrypted Key 20 12AB4EC21 + MK10 (card c) = Key 20 12AB4356
If you have a valid Master Key (Key10) and UA (Unique Address) then you can make an auto update file which will update the new key 20 or 21 when it is sent.
Now does THAT make more sense If not I'm happy to go through this and clarify things as long as you folks have a wish to understand more about what this hobby is really about.
Oh couple other things to mention (otherwise others here will tell me the above is wrong)
First thing.
In reality as many providers have millions of subscribers, they don't have time to send new operqational keys to every single card, one by one, using the UA (Unique Address)
So what they do in reality is update whole groups of cards at the same time (say 4096 cards per group) using the SA (Shared Address). If you understood post above you will realise that all cards from the same SA must have the same MK10!
Second thing (*)
There is some rumours/talk that since Conax changed cards in some SA groups, they have modified thier system to use BOTH key 20/21 to process the ECW. I have seen no evidence that this is true, but rumours persist.
If any good dudez out there know more about this then please post, or PM me, as I'm interested in this possibility.
And third thing
I know posting of keys (even fake ones) is not allowed here, but will mods pleas excuse my use of fake keys on this post? They were purely intended to demonstrate the pricinciples involved
It's probably not gonna be incredibly useful to anyone learning how Conax updates, but what the hell have it if you're interested.
2 lovely RSA lectures
Prime Number Hide-and-Seek: How the RSA Cipher Works
Table of Contents
* Preface: What is This?
* Introduction: The Idea of a Trapdoor Function
* Background, Part I: How to Calculate with Exponents
* Background, Part II: Modulus Arithmetic
* Background, Part III: The Fundamental Theorem of Algebra
* Background, Part IV: Relatively Prime Numbers
* Euler's Totient Function
* Euler's Totient Theorem
* Variations on a Theme
* The Plot Thickens
* Does This Really Work?
* Making a Pair of Keys
* An Example
* How to Crack RSA
* How to Make RSA Uncrackable
* Huge Exponents in Modulus Arithmetic
* Safety in Numbers
* References
Preface: What is This?
The RSA cipher is a fascinating example of how some of the most abstract
mathematical subjects find applications in the real world. Few are the
mathematicians who study creatures like the prime numbers with the hope or
even desire for their discoveries to be useful outside of their own domain.
But every now and then that is exactly what happens.
This text explains the mathematics behind RSA -- how and why it works. The
intended audience is just about anyone who is interested in the topic and
who can remember a few basic facts from algebra: what a variable is, the
difference between a prime number and a composite number, and the like.
The most important mathematical facts necessary for understanding RSA's
foundations are reviewed near the beginning. Even if you are familiar with
everything covered in these sections, I would recommend that you at least
skim through them.
In one or two places, I have specifically targeted an explanation to what I
consider to be the average computer programmer, leveraging analogous
concepts in programming and general mathematics.
Before getting started, I should make some observations on the mathematical
notation used here.
For the most part, where notations for the same idea differ between
standard mathematics and the common practices among computer programmers, I
have stuck with the mathematicians. This is, after all, a mathematical
subject. However, I have deviated in a few places where there was too much
opportunity for confusion. I have used * to denote multiplication, and have
completely avoided "implied" multiplication (i.e., using PQ as shorthand
for P * Q). Since not all web browsers can display superscripts, I have
used ^ to denote exponentiation. (This necessitates more parenthesizing
than would normally be used.) The mathematician's three-bar congruency
symbol is not available, so I have made do with = instead. Variables are
always named with a single capital letter.
Finally, please note that throughout the text I use the word number to
refer specifically to a positive integer -- what are sometimes referred to
as the natural numbers, or counting numbers.
------------------------------------------------------------------------
Introduction: The Idea of a Trapdoor Function
What a mathematician refers to as a function is very similar to a function
in computer programming. It is, in essence, an abbreviation. For example:
F(X) = 7 * X + 43.
If X happens to be 3, then F(X) will be 64. So, "F(3)" is shorthand for
"7 * 3 + 43".
The same function in a C program might look like:
int F(int x)
{
return 7 * x + 43;
}
Of course, in a computer program, functions are used to encapsulate all
kinds of algorithms, and frequently make use of external variables and the
like. In mathematics, however, a function is used solely for the number it
returns. And, given a certain number as input, they will always return the
same output. (Thus, rand() would not qualify as a mathematical function,
unless it were written so that the seed value was passed in as an input
parameter.)
Mathematicians often consider how to construct a function's inverse --
taking a function and making a new one that "goes in the other direction",
so to speak:
G(X) = (X - 43) / 7.
G(64) is equal to 3, and in general, G(F(X)) is equal to X. Therefore, G is
F's inverse. Not all functions are invertible, of course. Clearly, the
function:
F(X) = X * 0
cannot be inverted. (Because how could G(F(X)) return X when F(X) is always
zero?)
Usually, when you have a mathematical function for which an inverse does
exist, constructing it is not too difficult. In fact, it is often
transparent. Typically, you can just run through the steps backwards,
subtracting where the original function adds, and so on. But can it be done
for every invertible function?
To put the question in terms of programming, imagine that there are two
functions:
int foo(int x);
int bar(int x);
foo() and bar() work like mathematical functions -- they do nothing but
compute a return value, and given the same number for input, they will
always produce the same output. (And pretend for the moment that this is on
a machine where integers can be arbitrarily large.) Suppose you are told
that bar() is the inverse of foo(). The statement:
x == bar(foo(x))
is always true, as long as x meets foo()'s requirements for a valid
argument.
Now, imagine that you have the source code for foo(), but not for bar().
Can you write your own replacement for bar(), just by examining foo()?
It seems that you ought to be able to. There are no secrets as to what
foo() does, after all. You can run foo() with different inputs as many
times as you like. You already know that bar() exists, somewhere, so you
that it is possible to write. Is it guaranteed that you can reconstruct it?
Theoretically speaking, the answer is yes. Given such an function, it is
always possible to construct its inverse. However, if we also throw in the
tiny constraint that you have to finish before the heat-death of the
universe, the answer subtly changes.
There are some special functions that, though what they do is simple
enough, and how they do what they do is utterly transparent, figuring out
how to undo what they do is a diabolical task. Such a creature is a
trapdoor function. Anyone can fall through a trapdoor, but only those who
know where the hidden lever is can climb back out again.
In 1975, Whitfield Diffie, Martin E. Hellman, and Ralph Merkle realized
that a trapdoor function could be the basis for an entirely new kind of
cipher -- one in which the decoding method could remain secret even when
the encoding method was public knowledge. Diffie and Hellman published a
paper in 1976 that described this idea, and offered some examples of weak
trapdoor functions. And in 1977, Ronald L. Rivest, Adi Shamir, and Leonard
Adleman outlined, in an MIT technical memo, an excellent candidate that
became the basis for the RSA cipher.
What follows is a description of that function.
------------------------------------------------------------------------
Background, Part I: How to Calculate with Exponents
Here's a quick refresher on how to combine exponents. Recall that:
N^2 = N * N,
N^3 = N * N * N,
N^4 = N * N * N * N,
and so on. For example:
2^7 = 2 * 2 * 2 * 2 * 2 * 2 * 2 = 128.
If we fiddle with exponents for a bit, we will quickly realize that:
N^E * N = N^(E + 1).
So, for example:
2^7 * 2 = 128 * 2 = 256 = 2^8.
Building upon this, we can also see that:
N^E * N * N = N^(E + 2).
But N * N can also be written as N^2:
N^E * N^2 = N^(E + 2).
We can extrapolate from this, and derive a more general rule -- namely:
N^A * N^B = N^(A + B).
And, if we repeated this process on the next level up, we would find that:
(N^A)^B = N^(A * B).
These two simple facts are very useful when handling exponent-laden
formulas.
Background, Part II: Modulus Arithmetic
Most computer programmers are familiar with modulus as a "remainder"
operator, usually denoted by "%", which gives the remainder of an integer
division instead of the quotient. For example:
27 % 12 = 3.
Though the idea is the same, the mechanics here are slightly different from
what mathematicians refer to as modulus arithmetic. In essence, modulus
arithmetic consists of taking the infinitely long number-line and coiling
it around a finite circle. All the numbers that land on the same point
along the circle's edge are considered interchangeable, or congruent. Thus,
the analogue to the above example in modulus arithmetic would be expressed
as:
27 = 3 (mod 12),
or, in words:
27 is congruent to 3, modulo 12.
(Though note that mathematicians actually use a three-barred version of the
equal sign to indicate congruency.) In this case, 12 is the modulus that we
are working under, and the equation simply tells us that, under a modulus
of 12, 27 and 3 are considered to be the same number. Likewise:
11 + 16 = 3 (mod 12)
reads as:
11 plus 16 is congruent to 3, modulo 12.
Modulus arithmetic is sometimes called clockface arithmetic -- if it's
currently 11 o'clock, then 16 hours later it will be 3 o'clock. (Of course,
the analogy is less perfect when the modulus is something other than 12.)
An important feature of modulus arithmetic is that you can replace the
terms of an addition operation with congruent values, and still get the
right answer:
16 = 4 (mod 12), therefore
11 + 16 = 11 + 4 = 3 (mod 12).
Another example:
9835 = 7 (mod 12), and
1176 = 0 (mod 12), therefore
9835 + 1176 = 7 + 0 = 7 (mod 12).
Even better, this trick also works with multiplication:
9835 * 1176 = 7 * 0 = 0 (mod 12)
(and, if we check, we will see that, yes, 9835 * 1176 is 11565960, and
11565960 = 0 (mod 12)).
If our modulus was 10, then modulus arithmetic would be equivalent to
ignoring all but the last digit in our numbers:
37 = 7 (mod 10),
287 + 482 = 9 (mod 10), and
895 * 9836 = 0 (mod 10).
And, in a sense, a C program does all of its calculations in modulus
arithmetic. Since integer calculations in C are permitted to overflow, the
high bits silently falling off into the bit bucket, a C program using
32-bit integers is really doing all of its arithmetic modulo 2^32.
As you might imagine, some calculations that are time-consuming and produce
huge numbers become trivial in modulus arithmetic. The ability to reduce
values to their remainders before doing the actual calculation keeps the
calculations from getting out of hand.
Background, Part III: The Fundamental Theorem of Algebra
The Fundamental Theorem of Algebra states that for every number, there is
exactly one way to factor that number into primes -- and vice versa: every
selection of primes multiplies into a different number. For example:
1176 = 2 * 2 * 2 * 3 * 7 * 7, or
1176 = 2^3 * 3^1 * 7^2.
It is guaranteed that there is no other way to break 1176 into prime
factors. And, certainly, any time you take three 2s, two 7s, and a three,
you're always going to get 1176 when you multiply them together. The
Fundamental Theorem of Algebra assures us that both these things are true
for every number.
(By the way, this is one of the reasons that 1 is not considered to be a
prime number: if it were, then each number would have an infinite number of
prime factorizations, all differing by how many 1s were included. Instead,
1 is considered to have no prime factors at all, and we say that a number
is prime if it has exactly one prime factor -- namely itself.)
Put another way, the Fundamental Theorem of Algebra states that the set of
all numbers and the set of all selections of prime numbers are "isomorphic"
-- there is a perfect one-to-one mapping between the two. A number is
therefore defined by its prime factorization.
Background, Part IV: Relatively Prime Numbers
The greatest common divisor (abbreviated GCD) of two numbers is the largest
number that evenly divides into both of them. For example:
GCD(15, 10) = 5,
GCD(18, 10) = 2,
GCD(21, 10) = 1, and
GCD(170, 102) = 34.
Or, another way to look at it is to say that the GCD is the intersection of
the two numbers' set of prime factors:
GCD((2^3 * 3^1 * 7^2), (2^2 * 5^1 * 7^3)) = 2^2 * 7^2, so
GCD(1176, 6860) = 196.
When two numbers have no common factors, their GCD will be 1, and the two
numbers are said to be relatively prime (or coprime). For example, we can
see in our list up above that 21 and 10 are relatively prime.
Since a prime number has no factors besides itself, clearly a prime number
is relatively prime to every other number. And the same can be said of the
number 1.
Okay. Enough background material. Let's get to the good stuff.
------------------------------------------------------------------------
Euler's Totient Function
Euler's Totient Function is denoted by the Greek letter phi, and is defined
as follows:
phi(N) = how many numbers between 1 and N - 1 which are
relatively prime to N.
Thus:
phi(4) = 2 (1 and 3 are relatively prime to 4),
phi(5) = 4 (1, 2, 3, and 4 are relatively prime to 5),
phi(6) = 2 (1 and 5 are relatively prime to 6),
phi(7) = 6 (1, 2, 3, 4, 5, and 6 are relatively prime to 7),
phi( = 4 (1, 3, 5, and 7 are relatively prime to , and
phi(9) = 6 (1, 2, 4, 5, 7, and 8 are relatively prime to 9).
Here is the same definition expressed as C code:
phi = 1;
for (i = 2 ; i < N ; ++i)
if (gcd(i, N) == 1)
++phi;
(By the way, notice that phi(1) is specially defined to be 1.)
It should be easy to see that phi(N) will be N - 1 whenever N is prime.
Somewhat less obvious is the useful fact that phi(N) is also easy to
calculate when N has exactly two different prime factors:
phi(P * Q) = (P - 1) * (Q - 1), if P and Q are prime.
(The proof of this fact is left as an exercise for the reader.) Thus, for
example:
phi(15) = 2 * 4 = 8 (1, 2, 4, 7, 8, 11, 13, and 14).
The two prime factors cannot be the same number for this to work, and in
fact you can see above that phi(9) does not equal 4.
Euler's Totient Theorem
This theorem is one of the important keys to the RSA algorithm:
If GCD(T, R) = 1 and T < R, then T^(phi(R)) = 1 (mod R).
Or, in words:
If T and R are relatively prime, with T being the smaller number,
then when we multiply T with itself phi(R) times and divide the
result by R, the remainder will always be 1.
We can test this theorem on some smaller numbers for which we have already
calculated the totient. Using 5 for T and 6 for R, we get:
phi(6) = (2 - 1) * (3 - 1) = 1 * 2 = 2, so
5^(phi(6)) = 5^2 = 25, and
25 = 24 + 1 = 6 * 4 + 1, therefore
25 = 1 (mod 6).
Using 2 for T and 15 for R, we have:
phi(15) = (3 - 1) * (5 - 1) = 2 * 4 = 8, so
2^(phi(15)) = 2^8 = 256, and
256 = 255 + 1 = 17 * 15 + 1, therefore
256 = 1 (mod 15).
Variations on a Theme
Here again is the equation of Euler's Totient Theorem:
T^(phi(R)) = 1 (mod R)
(remembering that T < R, and T and R are relatively prime). Thanks to the
way that modulus arithmetic works on multiplication, we can easily see
that:
T^(phi(R)) * T^(phi(R)) = 1 * 1 (mod R),
which can be rewritten, using the laws of exponents, as:
T^(phi(R) + phi(R)) = 1 * 1 (mod R),
or:
T^(2 * phi(R)) = 1 (mod R).
If we ran through this sequence again, we would get:
T^(3 * phi(R)) = 1 (mod R).
Clearly, we could keep doing this as many times as we like. So, we can
expand on Euler's Totient Theorem, and state a more general corollary:
If GCD(T, R) = 1 and T < R, then T^(S * phi(R)) = 1 (mod R),
where S can be any number.
That's our first variation. Now, let's tweak this further by multiplying
both sides by T:
T^(S * phi(R)) * T = 1 * T (mod R).
Simplifying leaves us with:
T^(S * phi(R) + 1) = T (mod R).
If we repeat this, we will get:
T^(S * phi(R) + 1) * T = T * T (mod R),
or:
T^(S * phi(R) + 2) = T^2 (mod R).
Doing this yet again will give us:
T^(S * phi(R) + 3) = T^3 (mod R),
and so on.
What makes this so interesting is that S can be any number. It means that,
when calculating the value of:
T^E (mod R),
if E happens to be greater than phi(R), we can subtract phi(R) from E, and
keep on subtracting it until we have a number less than phi(R), and the new
formula will still produce the same value.
Guess what? This is just another way of describing modulus arithmetic. So,
what this boils down to is the rather surprising rule:
T^E = T^F (mod R) whenever E = F (mod phi(R)).
(again, as long as T < R, and T and R are relatively prime). In other
words, when doing modulus arithmetic, exponentiation works differently than
addition and multiplication. You can reduce an exponent, but you need to
use phi(R), and not R itself.
The Plot Thickens
We just blew past something very important. Let's back up and look at this
equation more closely:
T^(S * phi(R) + 1) = T (mod R).
Notice what we have here. We take a number, T, and raise it to a power, and
when we do the calculation in modulus arithmetic, we wind up with T again.
In short, we have a recipe for a function that returns its own input
(presuming that R has been chosen ahead of time, and T is relatively prime
to R).
If you're thinking to yourself, "What's so interesting about that?", then
consider what we would have if we broke this function up into two separate
steps. Specifically, let's imagine that we can find two new numbers P and Q
such that:
P * Q = S * phi(R) + 1, for some value of S that we choose.
Then we could rewrite:
T^(S * phi(R) + 1) = T (mod R)
as:
T^(P * Q) = T (mod R).
Now, this is equivalent to:
(T^P)^Q = T (mod R),
and this is something that can be broken up into two steps:
T^P = X (mod R), and then
X^Q = T (mod R).
Now, if you don't see the value in doing this, imagine now that the two
steps are performed on separate computers. And that X is sent from the
first computer to the second over an insecure phone line....
Does This Really Work?
T stands for the plaintext, the message that is to be sent. P, Q, and R
together form the cipher's keys -- P and R make up the public key, and Q
and R make up the private key. And X becomes the encrypted message.
Here, again, is the central equation that makes it all possible:
P * Q = S * phi(R) + 1.
Note here that P and Q will both automatically be relatively prime to
phi(R). (Why? Because their product, P * Q, is one more than a multiple of
phi(R). Any factors of P or Q must also be factors of P * Q. Any number
that is a factor of S * phi(R) + 1 can't also be a factor of phi(R).) This
is important, since it helps to assure us that a P and Q can actually be
found.
Imagine a clockface, with just an hour hand, and imagine yourself placing
the hour hand on midnight and then moving it forward by jumps, over and
over, each jump covering N hours. If you pick a value for N that is
divisible by 2 or 3 (the prime factors of 12), then you will find that you
will only hit certain numbers before you return to midnight, and the
sequence will then repeat. If N is 2, then the hour hand will visit 12, 2,
4, 6, 8, 10, 12, 2, 4, 6, 8, 10, 12 ...
If, however, your N is relatively prime with 12, then you will wind up
hitting every number exactly once before finally returning to midnight 12
jumps later. For example, using 7 for your N, the itinerary would be: 12,
7, 2, 9, 4, 11, 6, 1, 8, 3, 10, 5, 12, ... In addition, the order in which
you visit the numbers is entirely dependent on what value you pick for N.
In a similar vein, it is important that both P and Q be relatively prime to
phi(R). Because of this, we know that every possible value for T, when
raised to the power P modulo R, will land on a different number. (Remember
that when doing exponents in modulus arithmetic, it is actually phi(R), and
not R itself, that determines the length of the cycles.) If this weren't
true -- if P, for example, shared a factor in common with phi(R) -- then
some values for T could get mapped to the same value for X, and it would
clearly be impossible to tell which was originally which. There could not
be one value for Q that would correctly map X back to T every time.
The question of which T-values will wind up going to which X-values depends
entirely on the value used for P -- and here's the rub for the would-be
codebreaker: Just about every possible mapping of T-values to X-values does
in fact exist. Somewhere out there is a P that will make that mapping.
If this:
T^P = X
X^Q = T
was the cipher's scheme, there'd be no cipher. With P already being public
knowledge, it's tedious but no great trick to take an X and compute
backwards to T. But, instead, we have this:
T^P = X (mod R)
X^Q = T (mod R)
as the cipher's scheme, and that changes everything. The modulus arithmetic
erases too much information. There's no way to deduce how many times the
hour hand needs to spin around the clockface when it goes from X back to T.
Without knowing what Q is, a given X could wind up going to any of the
possible values for T.
But what is really maddening to our would-be codebreaker is that even when
T and P and X are all known, Q still can't be deduced! (Of course, it
actually can -- but not necessarily within anyone's lifetime. But we're
getting ahead of ourselves.)
So, let's see how to make this recipe work.
------------------------------------------------------------------------
Making a Pair of Keys
To construct our own personal cipher keys, we need an appropriate value for
R. So, we start by randomly picking two prime numbers, U and V, and
multiplying them together:
R = U * V.
There are two good reasons for selecting a value for R that has exactly two
prime factors. Not only do we have an easy formula for calculating phi(R):
phi(R) = (U - 1) * (V - 1),
but we also want R to be hard to factor. The fewer factors a number has,
the longer it takes to find them.
We then need to figure out values for P, Q, and S, such that:
P * Q = S * phi(R) + 1.
When the numbers have been chosen, P and R together become the public key,
and Q and R make up the private key. U, V, and S are no longer needed, and
can be forgotten.
An Example
In order to see all this in action, we want to stick with numbers that we
can actually work with. So, for our example, we will select the primes 5
and 7 to be our U and V. This gives R a value of 35, and:
phi(35) = (5 - 1) * (7 - 1) = 4 * 6 = 24.
Now, we need to find numbers to fit the equation:
P * Q = S * 24 + 1.
We'd prefer P and Q to not share any factors with each other, since that
would make it easier to derive one from the other. (And we certainly don't
want P and Q to be the same number, since that would turn our trapdoor
cipher into a garden-variety symmetric cipher!) So, P and Q should be
relatively prime. We will try assigning values to S and see what S * 24 + 1
equals. If we can divide the resulting number into two relatively prime
values, then we have a worthy pair.
2 * 24 + 1 = 49 = 7 * 7 (no, factors must be different)
3 * 24 + 1 = 73 = 73 (we need two numbers)
4 * 24 + 1 = 97 = 97 (ditto)
5 * 24 + 1 = 121 = 11 * 11 (nope)
6 * 24 + 1 = 145 = 5 * 29 (jackpot)
We could continue searching -- nothing requires us to take the first value
that works -- but this is fine for our purposes. So, we have 5 for P, our
public key, and 29 for Q, our private key.
To make our cipher work, you may recall that the values we use for T must
be less than R, and also relatively prime to R. We also don't want to use 1
for T, because 1 raised to any power whatsoever is going to remain 1. That
leaves us with 23 values we can use for T. We'll use the following
character set:
2 3 4 6 8 9 11 1213 16 17 1819 22 23 2426 27 29 3132 33 34
A B D E F G H I J K L M N O P R S T U V W Y Z
(We're missing a few letters, but this can be worked around with some
creative misspellings: KS for X, KW for Q, and K or S for C. In any case,
it's not important for this example.)
The message we will encrypt is "VENIO" (Latin for "I come"):
V E N I O
31 6 19 1222
To encode it, we simply need to raise each number to the power of P modulo
R.
V: 31^5 (mod 35) = 28629151 (mod 35) = 26
E: 6^5 (mod 35) = 7776 (mod 35) = 6
N: 19^5 (mod 35) = 2476099 (mod 35) = 24
I: 12^5 (mod 35) = 248832 (mod 35) = 17
O: 22^5 (mod 35) = 5153632 (mod 35) = 22
So, our encrypted message is 26, 6, 24, 17, 22 -- or "SERLO" in our
personalized character set.
When the message "SERLO" arrives on the other end of our insecure phone
line, we can decrypt it simply by repeating the process -- this time using
Q, our private key, in place of P.
S: 26^29 (mod 35) = 10819995774...2921981566976 (mod 35) = 31
E: 6^29 (mod 35) = 36845653286788892983296 (mod 35) = 6
R: 24^29 (mod 35) = 10620036506...3621199028224 (mod 35) = 19
L: 17^29 (mod 35) = 48196857210...1825223071697 (mod 35) = 12
O: 22^29 (mod 35) = 85164331908...9721106030592 (mod 35) = 22
The result is 31, 6, 19, 12, 22 -- or "VENIO", our original message.
How to Crack RSA
Now, let's switch hats. Imagine that we've just managed to pluck the
message "SERLO" off of our wiretap. By looking up the message's destination
in the public-key directory, we find that our message was encrypted with a
value of 35 for R and 5 for P. How do we go about decrypting it when we
don't know the value for Q?
Well, we know that that:
P * Q = S * phi(R) + 1.
We can divide both sides of the equation by P, which gives us a formula for
Q:
Q = (S * phi(R) + 1) / P.
S is also unknown, though, so we will have to try plugging in different
numbers for S, and look for values for Q that meet all the necessary
constraints.
(1 * 24 + 1) / 5 = 25 / 5 = 5 (no, same number as P)
(2 * 24 + 1) / 5 = 49 / 5 (doesn't divide evenly)
(3 * 24 + 1) / 5 = 73 / 5 (ditto)
(4 * 24 + 1) / 5 = 97 / 5 (ditto)
(5 * 24 + 1) / 5 = 121 / 5 (ditto)
(6 * 24 + 1) / 5 = 135 / 5 = 29 (this could be it!)
Each time we find a candidate for Q, we could test it out on a few
messages, and see if it works. (Note that, for example, when S = 11, Q will
have a value of 53, which also meets all the constraints, but does not
decrypt correctly with P = 5.) If 29 hadn't worked and we needed to
continue the search, it would be pretty obvious that we only needed to test
every fifth number, since those are the only numbers which will give us a
result that is evenly divisible by 5. So, even though this process involves
a brute-force search, it is very simple and very fast.
So what's the catch? Well, in order to do any of this, we first need to
know the value of phi(R). Of course, we already know that R has exactly two
prime factors, so calculating phi(R) is a snap once we know what those
factors are.
Famous last words.
------------------------------------------------------------------------
How to Make RSA Uncrackable
Of course, in our case the factors of R can be found by consulting a times
table. So it's not much of a challenge. (For that matter, since we're
encrypting one character at a time, our coded messages would also be
vulnerable to good old-fashioned cryptanalysis).
To make it less easy to find R's factors, we need to pick larger prime
numbers for U and V to begin with. If, instead of 5 and 7, we had chosen
673 and 24971, we would have a value of 16805483 for R, and phi(R) would be
16779840. (This would also give us enough room to encrypt three bytes at a
time, which pretty much ruins any hope of cryptanalysis.) Looking for a P
and Q pair is no longer something you want to do with pencil and paper, of
course, but it took me less than three minutes to find the usable pair 397
and 211333 -- including the time it took to write and debug a Perl script.
On the other hand, it also took me less than three seconds to run "factor"
on 16805483 to obtain 673 and 24971. Armed with those numbers, it wouldn't
take long to derive 211333 from 397. So even these numbers aren't close to
being large enough. We need really big numbers.
Well, we can certainly find huge values for R that are difficult to factor.
But how far can we go before it becomes too difficult for us to use the
numbers in the first place?
Huge Exponents in Modulus Arithmetic
The problem is this: The bigger R gets, the bigger P and Q will be, and P
and Q are to be used as exponents! Even the relatively tame-looking:
9^(9^9)
produces a number over 350 million decimal digits long. How are we going to
be able to encrypt anything without needing terabytes of storage?
The trick is that we only need to calculate these exponential values modulo
R. As always, modulus arithmetic simplifies things a great deal.
Let's revisit our example, and look at how we could decrypt the first
number, 31, remembering that R = 35 and Q = 29:
31^29 (mod 35) = ?
To start with, we look at Q's binary representation. 29 in binary is 11101,
which means that:
29 = 16 + 8 + 4 + 1, or
29 = 2^4 + 2^3 + 2^2 + 2^0.
We can now break the exponential calculation apart into several smaller
ones:
31^29 = 31^(2^4 + 2^3 + 2^2 + 2^0)
= 31^(2^4) * 31^(2^3) * 31^(2^2) * 31^(2^0)
= 31^(2 * 2 * 2 * 2) * 31^(2 * 2 * 2) * 31^(2 * 2) * 31
= (((31^2)^2)^2)^2 * ((31^2)^2)^2 * (31^2)^2 * 31.
This may look like anything but an improvement, at first. But on a closer
examination, you'll see that we actually have many repeated subterms. This
simplifies matters, particularly when we take advantage of the fact that we
are calculating in modulo 35.
We compute the first square in modulus arithmetic:
31^2 = 961 = 16 (mod 35).
By substituting this value into our equation:
31^29 = (((31^2)^2)^2)^2 * ((31^2)^2)^2 * (31^2)^2 * 31 (mod 35),
we get:
31^29 = ((16^2)^2)^2 * (16^2)^2 * 16^2 * 31 (mod 35).
Now by computing that square:
16^2 = 256 = 11 (mod 35),
we will have:
31^29 = (11^2)^2 * 11^2 * 11 * 31 (mod 35).
We keep simplifying in the same fashion:
11^2 = 121 = 16 (mod 35), and
16^2 = 256 = 11 (mod 35),
and so:
31^29 = 16^2 * 16 * 11 * 31 (mod 35)
= 11 * 16 * 11 * 31 (mod 35).
We can continue to take advantage of the modulus when we do the final
multiplications:
31^29 = 11 * 16 * 11 * 31 (mod 35)
= 11 * 16 * 341 (mod 35)
= 11 * 16 * 26 (mod 35)
= 11 * 416 (mod 35)
= 11 * 31 (mod 35)
= 341 (mod 35)
= 26 (mod 35).
Lo and behold: 26, the same result as when we did it the hard way.
This binary technique is really no different than how computers normally
compute integer powers. However, the fact that we can break the process
down to successive multiplications allows us to apply the modulus at every
step of the way. This assures us that at no point will our algorithm have
to handle a number larger than (R - 1)^2.
Safety in Numbers
Okay. So we know that the process of encryption and decryption is still
practical, even if R is immense. But all of this is moot unless we can
still generate the keys. If we want R to be so big that it can't be
factored easily, how are we going to find it in the first place?
Well, it turns out that there is an interesting little asymmetry here.
There happen to be relatively cheap ways to test a number for primality.
One of the most famous is based on what is called Fermat's Little Theorem.
Here is the version of this Theorem that we're interested in:
If P is prime, then N^(P - 1) = 1 (mod P) is true for every
number N < P.
(If this seems suspiciously reminiscent of Euler's Totient Theorem, it
should. Euler was the first person to publish a proof of this Theorem, and
his Totient Theorem is a generalization of Fermat's. You can see this for
yourself by remembering that phi(P) = P - 1 when P is prime.)
Of course, from a mathematician's point of view, this theorem is mainly
useful for proving that a given number is composite. For example, it just
so happens that:
4^14 (mod 15) = 268435456 (mod 15) = 1,
even though 15 is no prime. Nonetheless, it is also true that:
3^14 (mod 15) = 4782969 (mod 15) = 9, and
5^14 (mod 15) = 6103515625 (mod 15) = 10.
On the other hand, 17, which is prime, results in 1 every time:
3^16 (mod 17) = 43046721 (mod 17) = 1,
4^16 (mod 17) = 4294967296 (mod 17) = 1,
5^16 (mod 17) = 152587890625 (mod 17) = 1, and so on.
So, if we want to know if a number is prime, we can run it through this
test, using (say) 2 as the base. If anything besides 1 results, we know
with certainty that the number is composite. If the answer is 1, however,
we try the test again with 3, and then 4, and so on. If we keep getting
back 1 as the result, it soon becomes astronomically unlikely that the
number is anything but prime. This doesn't constitute proof, mathematically
speaking, but it certainly works for our purposes.
There are other tests for primality, some of which are faster. But they all
have at least one thing in common with this test: When they reject a
number, it tells us only that the number can be factored. The test results
give us no information at all as to what the factors might be. How
unfortunate!
Unfortunate for the mathematicians, that is. Very fortunate for us.
The basic truth is that, in order to find the factors of a composite
number, we're pretty much stuck with using brute force: Divide the number
by all the primes you can get your hands on until one of them goes in
evenly. There are ways to improve on this approach (the Number Field Sieve
currently being the best), but they are complicated, and all they do is
allow you to narrow the scope of the search. They don't reduce the search
enough to make this problem tractable in general.
Nor is it likely that new approaches will, either! The real issue is that
the encrypting and decrypting algorithms have a running time that is linear
with respect to the length of R. That is to say, doubling the number of
digits in R doubles the amount of time (roughly) needed to encrypt,
decrypt, and to select the two primes to make a key with. But the
algorithms for factoring R have a running time that is exponential with
respect to the length of R. That is to say, the time (roughly) doubles with
every few digits! (Because every digit added to R makes it ten times
larger, and thus multiplies the number of potential candidates for its
measly two factors.)
So if a new technique is suddenly found that makes it a trillion times
faster to factor a number, all we have to do is increase the size of R we
use by enough digits, and the situation will be right back where it started
-- and all it means to us is that it takes a little bit longer to send and
receive our messages. Already some people are using keys that, in order to
factor with the Number Field Sieve, would require more energy than exists
in the known universe.
An illustration: To the best of my knowledge, the number used as the
modulus for the RSA-140 challenge is the largest general number than has
been independently factored. (By general, I'm excluding creatures like
Mersenne numbers and Fermat numbers, which have specialized factoring
techniques that are inapplicable elsewhere.) It was completed on February
2, 1999. Now, the record previous to this was the RSA-130 number, and the
process of factoring it was estimated as taking a total of 1000 MIPS-years
of computer time. RSA-140, a number only 10 decimal digits longer, required
twice that amount.
This, finally, is the heart of what makes RSA a trapdoor function: the gap
between obtaining a number with two prime factors, and rediscovering the
factors from the number itself. And the gap just keeps expanding as the
numbers get larger.
The breakthrough that would completely destroy RSA's security would be an
algorithm that actually produced a number's factors directly, instead of
merely narrowing the search's scope. Such a thing has not been proven
impossible, and it would probably be very hard to do so. But considering
the renewed attention that has been focused on this problem in the last two
decades, the likelihood of the existence of such an algorithm is once again
starting to appear quite remote. Discovering one would change the face of
number theory as much as RSA has changed the face of cryptography.
However -- if this were to happen, there are other trapdoor functions out
there, waiting to be found. Whatever the future of RSA may be, the trapdoor
cipher has certainly changed the face of cryptography forever.
------------------------------------------------------------------------
References
1. Clawson, Calvin C.: "Mathematical Mysteries", 1996, Plenum Press.
(Clawson devotes an entire chapter to the mathematics behind RSA, and it is
this that gave me the inspiration to create this text.)
2. Gardner, Martin: "Penrose Tiles to Trapdoor Ciphers", 1989, W.H. Freeman
& Co. (This is another anthology of Gardner's wonderful columns for
"Scientific American", and includes the column which was the first widely
published description of the RSA cipher -- the one which set the NSA to
frantically running around in circles.)
3. Ribenboim, Paulo: "The Little Book of Big Primes", 1991,
Springer-Verlag. (The title should actually be "The Little Book of Big
Number Theory" -- the book is chock full of theorems and conjectures that
relate to prime numbers.)
4. Wells, David: "The Penguin Dictionary of Curious and Interesting
Numbers", 1986, Penguin Books. (I had to pull this out at the last minute
to find out how many digits were in 9^(9^9). For the curious whose
libraries lack this little gem, the exact number of digits is 369693100.)
Texts
Brian Raiter
Muppetlabs
Ø #public.ms
This entire document has been produced using 'MAPLE', the 'Computer
Algebra Software' which is installed on computers in St. Patrick's
computer laboratory. Anyone who is interested in finding out about
how to obtain MAPLE is welcome to ask me about it.
___________________________
PUBLIC LECTURE. WED. 6th. NOVEMBER 1996.
ST. PATRICK'S COLLEGE, DRUMCONDRA, DUBLIN 9.
LECTURE TITLE: PRIME NUMBERS and
PUBLIC-KEY CRYPTOGRAPHY
LECTURER: Dr. JOHN COSGRAVE,
MATHEMATICS DEPARTMENT,
ST. PATRICK'S COLLEGE,
DRUMCONDRA,
DUBLIN 9,
IRELAND.
E-mail: [email protected] (home)
___________________________________________
AIM of LECTURE: To explain the fundamental concept of 'public-key cryptography' (a revolutionary development of the past twenty years), and to show how 'prime' numbers have played an integral role in its development.
PLAN of LECTURE:
1. What is 'Cryptography'? A very brief history for the period to 1976 A.D.
2. The fundamental idea of public-key cryptography (Diffie and Hellman, 1976).
3. A brief mathematical interlude ('modular exponentiation').
4. The realization of public-key cryptography (Rivest, Shamir and Adleman, 1977).
5. Fundamental mathematical ideas for public-key.
___________________________________________
1. What is Cryptography? A brief history.
[ Etymology: from the Greek 'kryptos logos', meaning 'hidden word'. So 'cryptography' is 'secret' or 'hidden' writing. ]
I will speak on this (and am not making it part of my text, which I only regard as the 'bones' of my talk) for about five/ten minutes. At the end of this part of my lecture the key terms (no pun intended) will be:
a. plaintext (the ordinary text)
b. encryption key (what someone applies to plaintext to disguise it)
c. ciphertext (the encrypted form of the text)
d. decryption key (what one applies to ciphertext to recover the plaintext)
___________________________________________
2. The fundamental idea of public-key cryptography
(Diffie and Hellman, Stanford University, 1976)
Their fundamental paper:
'New Directions in Cryptography', IEEE Transactions on Information Theory,
Vol. IT-22, No. 6, November 1976, 644-654. (IEEE is the Institute of Electronic
and Electrical Engineers.)
The opening sentence from their paper read: "We stand today on the brink
of a revolution in cryptography."
In this paper they proposed the IDEA (and much, much more as well) of
'public-key' (as opposed to the classical 'private-key') cryptography.
I will talk about this in my lecture.
____________________________________________
3. A brief mathematical interlude ('modular exponentiation')
Question: What remainder does the number 34 'leave' when divided by 13?
That's easy. 34 = 13*2 + 8, and so on division by 13 the number 34 'leaves' remainder 8.
Dividing numbers by 13 is called 'doing modular arithmetic' with 'modulus' 13, and this is how one does it (in MAPLE) with the above example, followed rapidly with some other examples (which I will ask YOU to do in your head before I use MAPLE):
> 35 mod 13;
9
> 123437652596959161941949 mod 5461385845;
1376393784
> 100000000000000 mod 100000000;
0
> 10000000000000000018 mod 100000000000;
18
>
Another question: What remainder does the number 3 to the power of 5 leave on division by 13?
That's also easy. 3^5 = 243 = 13*18 + 9, and so on division by 13 the number 3 to the power of 5 leaves remainder 9. Dividing numbers by 13 is - as you know - 'doing modular arithmetic' with 'modulus' 13; dividing powers of numbers by 13 is called 'doing modular exponentiation' with modulus 13, and it can of course be done by the MAPLE command which you have already seen:
> 3^5 mod 13;
9
> 5^3 mod 13;
8
> 12321^3 mod 873;
396
>
But how about finding - for example - the remainder that the number 123456789123456781234567 to the power of 987654321987654321987654321 leaves on division by 122333444455555?
Let's try it:
> 123456789123456781234567^9876543219876543219876543
21 mod 122333444455555;
Error, integer too large in context
>
What does that "Error, object too large" mean?
It means that the number 123456789123456781234567^9876543219876543219876543
21 is too large for MAPLE to handle. But not only is it too large for MAPLE to handle, it is in fact SO large that even if it were calculated it would require years to write it out even at a rate of billions of digits per second.
But - as you will see later - this (the finding of the remainder) is precisely the sort of calculation that one needs to be able to do in 'public-key' cryptograhy. Number theorists have known for many years how to do this sort of calculation. It is done by a combination of methods: ordinary 'modular' arithmetic, together with what is called the 'square and multiply' method. The details of this would take some time to explain, and so you must allow me to skip gently by them (the details are actually quite simple, and I teach them to my students).
MAPLE has an inbuilt facility for doing 'modular exponentiation', and here I illustrate it with a few examples, starting with the ones with which you are already familiar, and then moving on to the one that led to the "Error, object too large":
> 3&^5 mod 13;
9
> 5&^3 mod 13;
8
> 12321&^3 mod 873;
396
>
And now - much more dramatically - the earlier "Error" one, and onother one:
> 123456789123456781234567&^987654321987654321987654 321 mod 122333444455555;
30331953000667
>
Instantly!
You see the difference in the 'commands'?
The earlier command was of the form a^b mod m. In that form MAPLE was being asked to FIRST calculate a^b, and THEN calculate the remainder on division by m.
The latter command was of the form a&^b mod m. In that form MAPLE was being asked to use modular arithmetic TOGETHER with the (INCREDIBLY FAST) square-and-multiply method.
One more example:
> 2086822056296502560265&^3548276254987776266 mod 931987294968252720194941649999;
568750443556679669023065555056
>
Later you will see why we need to be able to do such calculations. ____________________________________________
4. The realization of public-key cryptography by
Rivest, Shamir and Adleman of MIT, 1977.
(MIT = the Massachusetts Institute of Technology)
Their fundamental paper:
'A method for obtaining digital signatures and public-key cryptosystems', Communications of the ACM (Association for Computing Machines), Vol. 21, (197, 120-126.
Their paper began: "An encryption method is presented with the novel property that publicly revealing an encryption key does not thereby reveal the corresponding decryption key. This has two important consequences:
(1) Couriers or other secure means ane not needed to transmit keys, ... .
(2) A message can be "signed" using a privately held encryption key. Anyone can verify this signature using the corresponding publicly revealed encryption key.
Signatures cannot be forged, and a signer cannot later deny the validity of his signature. This has obvious applications in "electronic mail" and "electronic funds transfer" systems ... .
___________________________________________
The work of Rivest, Shamir and Adleman first gained widespread public attention when it was brilliantly explained by Martin Garnder in his 'Scientific American' Mathematical Games column in the August 1977 issue. The header for that article read:
"A new kind of cipher that would take millions of years to break"
It was in that article that the famous RSA_129 'challenge number' first made its appearance. I will have things to say about that later ... .
___________________________________________
WHAT IT'S ALL GOING TO BE ABOUT. In a nutshell, what I am going to attempt to explain to you reduces to this: You know what a prime number is (2, 3, 5, 7, 11, 13, ... ). There are an 'infinite' number of them (Euclid), and if I were to choose two SMALL primes and NOT reveal them to you, BUT told you their product, THEN you would have NO difficulty in telling me what the two primes were. Say, for example, I told you their product was 91; then after a moment's reflection you would be able to tell me that the primes I had chosen were 7 and 13.
BUT if I were to choose two 'LARGE' primes and not reveal them to you, and I told you their product, then you (and not only you, but - for example - the US National Security Agency) would find it VIRTUALLY IMPOSSIBLE (in a sense which I will be more explicit about later) to tell me what the two primes were. It is this (current) VIRTUAL IMPOSSIBILITY that Rivest, Shamir and Adleman exploited to create an "unbreakable cryptographic protocol" (there are reservations which I will explain later in the lecture).
So, keep your eye open for the PRODUCT of TWO prime numbers in what follows ... .
_______________________________
Here I will throw you in at the deep end, and then embark on a mathematical journey at the end of which I hope you will 'know'.
" We shall not cease from exploration
And the end of all our exploring
Will be to arrive where we started
And know the place for the first time. "
(T.S. Eliot)
________________________________
The first thing I do (and this is elementary) is to give instructions for converting plaintext into numerical form, according to the associations: a with 1, b with 2, ... , z with 26, A with 27, B with 28, ... , Z with 52, ` (the 'backward quote' sign) with 53, 1 with 54, 2 with 55, ... , 9 with 62, 0 with 63, - (the minus sign) with 64, ... , ( - the left round bracket - with 75, ... , a 'space' with 79, ... , and so on.
[ These instructions were communicated to me - via the Internet - by Joe Riel, an engineer working in California. I sent out an enquiry via the 'Maple Users Group' asking for help with this, and within hours I had several helpful responses, the best of which was Joe Riel's. ]
The following is simply to instruct MAPLE as to which letters (small and large case), numerals, punctuation marks, etc. I wish to use:
> `crypt/alphabet` :=
> `abcdefghijklmnopqrstuvwxyz`
> .`ABCDEFGHIJKLMNOPQRSTUVWXYZ`
> .```[email protected]#$£%^&*()_+`
> .` ,./<>?;':"[]{}|`:
>
The following sets up the association between the terms of the 'crypt/alphabet'
and the numbers 1 to 95.
> ### WARNING: semantics of type `string` have changed
> to_number := proc(st, string) local ll, nn, ss, ii;
> global `crypt/alphabet`; ll := length(st);
> if ll = 0 then RETURN(0) fi; nn := 1;
> for ii to ll do ss := SearchText(substring(st, ii .. ii),
> `crypt/alphabet`);
> if not type(ss, numeric) or ss = 0 then
> ERROR(`the letter `.(substring(st, ii .. ii))
> .` is not in the alphabet`)
> fi; nn := 100*nn + ss od;
> nn - 10^(2*ll) end:
>
Some examples:
> to_number(`Welcome to St. Patrick's College`);
49051203151305802015804520828042012018090311881980
29151212050705
>
And a much longer one:
[Added afterwards for people to whom I send this worksheet: This next one may lead to an 'Error' message ('strings') for you, and you may need to change it. I just wanted to write a message with a great variety of signs in it.]
> to_number(`There are - at the moment - US$1.60 to IR£1 (the Irish 'punt'). In one of George Orwell's letters (in the 4-volume Penguin edition) you may read that at one time the rate was US$5 to St£1. Do you remember the term 'half a dollar'? It was two shillings and sixpence`);
46080518058001180580648001208020080580131513051420
80648047457054\
82596380201580354471548076200805803518091908808816
21142088\
77828080351480151405801506803305151807058041182305
12128819\
80120520200518198076091480200805805764221512211305
80420514\
07210914800504092009151477802515218013012580180501
04802008\
01208001208015140580200913058020080580180120058023
01198047\
45705880201580452071548280803015802515218018051305
13020518\
80200805802005181380880801120680018004151212011888
86803520\
80230119802023158019080912120914071980011404801909
24160514\
03056767
>
The '6767' at the end of the output represents '', the double exclamation mark.
And now some instructions to recover a text from its numerical form:
> from_number := proc(nn, integer)
> local ss, mm, ll, pp, ii, ans;
> global `crypt/alphabet`; mm := nn;
> ll := floor(1/2*trunc(evalf(log10(mm))))+1;
> ans := ``; for ii to ll do mm := mm/100;
> pp := 100*frac(mm);
> if pp > length(`crypt/alphabet`) then ERROR
> #(`there is no letter in the alphabet corresponding `
> #.`to the number `.(convert(pp, string))) fi;
> (`there is NO meaningful text corresponding`
> .` to the number you have inputted`) fi;
> ss := substring(`crypt/alphabet`, pp..pp);
> ans := cat(ss, ans); mm := trunc(mm)
> od; ans end:
>
Some examples:
> from_number(950102030495);
|abcd|
>
And now I take the number you have just seen, and adjoin an
extra 96 at the end:
> from_number(95010203049596);
Error, (in from_number) there is NO meaningful text corresponding to the number you have inputted
>
> from_number(30050118803615081481805115211880120503
202118058023011980191580828282);
Dear John, Your lecture was so ...
>
So much for just taking a text and recasting it in numerical form according to the above associations. Now to get down to the real business of sending public-key encrypted messages, and their decryption:
A Cookbook for public-key encryption and decryption.
I am going to show you how SOMEONE can send ME a message that THEY encrypt by the 'RSA cryptographic protocol' (as it is called, after its creators, Rivest, Shamir and Adleman), and which THEY do NOT ANYONE TO UNDERSTAND BUT ME, and show you what I then do to decrypt THEIR message.
It is to be understood that the above numerical associations are already agreed upon.
BEFORE anyone can send me an RSA-encrypted message they have to know what is called my 'public-key'. My public key is a pair of numbers (n, e). The 'n' is what is called my 'public modulus', and the 'e' is my 'public encryption power'. These are formed as follows:
The first step is to choose a (reasonably big - more on how big later) random prime number:
> p:=nextprime(5678289499759252694659696599956594847
4734464644);
p := 56782894997592526946596965999565948474734464699
>
and then similarly choose another prime number:
> q:=nextprime(7529658762856826582828448562554749438
4373773574447);
q := 75296587628568265828284485625547494384373773574459
>
THOSE 2 PRIME NUMBERS ARE KEPT SECRET.
And then I multiply those two prime numbers together:
> n:=p*q;
n := 42755582289900163331305876195209620856222072837410
274660074\
83764886188191592850870337425183522841
>
That number 'n' is my PUBLIC MODULUS ('public' in the sense that I do NOT care who knows its value).
Next I form my a certain number 'e', my 'public encryption power'.
That is formed as follows:
First I form a VERY SPECIAL number called 'phi_n' which, like p and q above,
is ALSO KEPT SECRET:
> phi_n:=(p - 1)*(q - 1);
phi_n := 42755582289900163331305876195209620856222072836656
74095\
483917906530957109001303810004576675483684
>
Having formed phi_n I then form my 'public encryption exponent' 'e'. That is specially chosen so that there is NO whole number larger than 1 which is a factor of BOTH e AND phi_n. [ And so - for example - IF p and q had been 19 and 23, then one would NOT choose e to be 15 because 3 is a factor of BOTH 15 AND (19 - 1)*(23 - 1). Whereas IF e had been chosen to be 7 (say), then it would be alright. ]
In practice I choose e to be a large randomly chosen prime:
> e:=nextprime(75859825925924926296969);
e := 75859825925924926297033
>
I have to be CERTAIN that there is NO whole number larger than 1 which is a factor of BOTH e and phi_n. That involves some standard mathematics (called the 'Euclidean algorithm') - the details of which need not concern you - and is checked by:
> igcd(e, phi_n); # 'igcd' stands for 'integer greatest common divisor'
1
>
The MEANING of that '1' is that the ONLY factor of BOTH e and phi_n is 1, and so
here I am safe.
[ Aside: here two examples for you to see, with smaller whole numbers involved: ]
> igcd(15, 22);
1
> igcd(15, 21);
3
>
Having chosen my PUBLIC encryption exponent e, I then proceed to calculate my 'PRIVATE decryption exponent' 'd'. That number d is the UNIQUE number BETWEEN 1 and phi_n such that the product of e and d leaves remainder 1 on division by phi_n. A FUNDAMENTAL mathematical point is that d can ONLY be calculated by someone who KNOWS the value of phi_n, or, what amounts to the same thing, the values of p and q.
Now that I have chosen - and made known my RSA 'public-key' (n, e) - I am ready to receive RSA-encrypted messages.
So, suppose someone (YOU, let us say) wanted to send ME an RSA-encrypted message, whose plaintext was: The money is now in your Swiss account.
This is what you would do:
First you would cast your text into numerical form, using the above agreed instructions:
> numerical_form_of_text:=to_number(`The money is now in your Swiss account`);
numerical_form_of_text := 46080580131514052580091980141523800914\
80251521188045230919198001030315211420
>
and then you would check to see how many digits are in the numerical form of your text:
> length(numerical_form_of_text);
76
>
You also check how many digits my 'public modulus' n has:
> length(n);
97
>
With the number which is the numerical form of your text being LESS than my public modulus you are now ready to send me your message (I will explain in my lecture what you do otherwise).
This is what you do:
You
There are currently 1 users browsing this thread. (0 members and 1 guests)