[ Pobierz całość w formacie PDF ]

to the world (that is why such systems are called public key systems) and
invite anybody who wants to spy for him to send him secret messages in total
con dence.
It is all very well to describe such a code but do they exist? There is
very strong evidence that they do but so far all mathematicians have been
able to do is to show that provided certain mathematical problems which are
believed to be hard are indeed hard then good codes exist.
The following problem is believed to be hard.
Problem Given an integer N which is known to be the product N = pq of
two primes p and q, nd p and q.
Several schemes have been proposed based on assumption that this factori-
sation is hard. (Note however that it is easy to nd large primes p and q.)
We give a very elegant scheme due to Rabin and Williams. It makes use of
some simple number theoretic results from 1A and 1B.
The following result was proved towards the end of the course Quadratic
Mathematics and is, in any case, easy to obtain by considering primitive
roots.
Lemma 11.2. If p is an odd prime the congruence
x2 d mod p
is soluble if and only if d 0 or d(p;1)=2 1 modulo p.
Lemma 11.3. Suppose p is a prime such that p = 4k ; 1 for some integer
k. Then if the congruence
x2 d mod p
has any solution, it has dk as a solution.
We now call on the Chinese remainder theorem.
47
Lemma 11.4. Let p and q be primes of the form 4k ; 1 and set N = pq.
Then the following two problems are of equivalent di culty.
(A) Given N and d nd all the m satisfying
m2 d mod N:
(B) Given N nd p and q.
(Note that, provided that that d 6 0, knowing the solution to (A) for any
d gives us the four solutions for d = 1.) The result is also true but much
harder to prove for general primes p and q.
At the risk of giving aid and comfort to followers of the Lakatosian heresy
it must be admitted that the statement of Lemma 11.4 does not really tell
us what the result we are proving is, although the proof makes it clear that
the result (whatever it may be) is certainly true. However, with more work,
everything can be made precise.
We can now give the Rabin-Williams scheme. The spy-master A selects
two very large primes p and q. (Since he has only done an undergraduate
course in mathematics he will take p and q of the form 4k ; 1.) He keeps the
pair (p q) secret but broadcasts the public key N = pq. If B wants to send
him a message she writes it in binary code splits it into blocks of length m
with 2m
2
B computes sj such that rj sj modulo N and sends sj. The spy-master
(who knows p and q) can use the method of Lemma 11.4 to nd one of four
possible values for rj (the four square roots of sj). Of these four possible
message blocks it is almost certain that three will be garbage so the fourth
will be the desired message.
If the reader re ects, she will see that the ambiguity of the root is gen-
uinely unproblematic. (If the decoding is mechanical then making each block
start with some xed sequence of length 50 will reduce the risk of ambigu-
ity to negligible proportions.) Slightly more problematic, from the practical
point of view, is the possibility that some one could be known to have sent a
very short message, that is to have started with an m such that 1 m N1=2
but provided sensible precautions are taken this should not occur.
12 Commutative public key systems
In the previous sections we introduced the coding and decoding functions
;1
KA and KA with the property that
;1
(pKA)KA = p
48
and satisfying the condition that knowledge of KA did not help very much in
;1
nding KA . We usually require, in addition, that our system be commutative
in the sense that
;1
(pKA )KA = p:
;1
and that knowledge of KA does not help very much in nding KA. The
Rabin{Williams scheme, as described in the last section, does not have this
property.
Commutative public key codes are very exible and provide us with simple
means for maintaining integrity, authenticity and non-repudiation. (This is
not to say that non-commutative codes can not do the same simply that
commutativity makes many things easier.)
Integrity and non-repudiation Let A `own a code', that is know both
;1 ;1
KA and KA . Then A can broadcast KA to everybody so that everybody
;1
can decode but only A can encode. (We say that KA is the public key and
KA the private key.) Then, for example, example, A could issue tickets to
the castle ball carrying the coded message `admit Joe Bloggs' which could be
read by the recipients and the guards but would be unforgeable. However,
for the same reason, A could not deny that he had issued the invitation.
Authenticity If B wants to be sure that A is sending a message then B can
send A a harmless random message q. If B receives back a message p such
;1
that pKA ends with the message q then A must have sent it to B. (Any
body can copy a coded message but only A can control the content.)
;1
Signature Suppose now that B owns a commutative code pair (KB KB )
;1
and has broadcast KB . If A wants to send a message p to B he computes
;1 ;1 ;1
q = pKA and sends pKB followed by (qKA )KB . B can now use the fact
that
;1
(qKB )KB = q
;1
to recover p and q. B then observes that qKA = p. Since only A can
produce a pair (p q) with this property, A must have written it.
There is now a charming little branch of the mathematical literature
based on these ideas in which Albert gets Bertha to authenticate a mes-
sage from Caroline to David using information from Eveline and Fitzpatrick,
Gilbert and Harriet play coin tossing down the phone and Ingred, Jacob,
Katherine and Laszlo play bridge without using a pack of cards. However a
49
cryptographic system is only as strong as its weakest link. Unbreakable pass-
word systems do not prevent computer systems being regularly penetrated
by `hackers' and however `secure' a transaction on the net may be it may
still involve a rogue on one end and a fool on the other. [ Pobierz całość w formacie PDF ]

zanotowane.pl

doc.pisz.pl

pdf.pisz.pl

qus.htw.pl