Setting: A bank wants to communicate with its customers
over the internet.
It does not want to set up different keys for each customer, a lot of work.
It does not want to risk a customers secret key being stolen or otherwise compromized.
It will be notationally convenient below to abbreviate
as
and
as
and
as
which is consistant with 1.
Methodology: The bank tells the world about and if a customer wants to communicate a message ,
the customer first computes and then transmits . The bank then "receives" the message by computing ).
Issues:
Knowing , it should be hard to determine .
The message should still contain some private information, maybe an account number, so that a customer's account is not compromised.
Digital Signatures:
PKE can be used for two way secret communication, between bank
and
bank
,
as follows:
Assume bank
has a PKE
(
,
) and bank
has a PKE
(
,
).
Assume the Messages are the same for both PKEs , moreover assume
for
both.
Finally assume,
Note that this would be true for 2 RSA schemes (see below).
Methodology: bank wishes to send a secret message , using it computes and transmits it. To read the message bank computes
Again, bank knows but not and bank knows but not .
Methodology: Our calculations are in unless noted as .
Choose where are primes and
Choose such that , and let .
for
some
.
The key observation is that if
for
then by the Fermat--Euler Theorem:
To allow anybody to securely transmit messages to you:
Tell the world and . Assume somebody wants to send the message to you privately, tell them to compute
and transmit
To decode the message received:
Compute
To break the code:
Since people know
and
, they need to calculate
, and to do that they need to calculate
In particular factor
, which can be difficult.
Some additional Notes. from a course I taught a few years back.
An original example from Rivest, Shamir, Adleman(1978):
The Alphabet Encoding:
The Message:
ITS
ALL GREEK TO ME
The Message encoded in blocks of 2(with padding the last ):
- - - - - -- - - - - -
Note: Encoding in blocks of 2 and then enciphering the block is a bit idiosyncratic. I chose to reproduce the original example.
What makes this work is that the biggest, thus encoded message (ZZ) ,considered as a number
Of course, the price paid is that the deciphered message may have an extra blank at the end.
- - - - - - - - - - - - - - - - - -
IT :Enciphered
The Message Enciphered :
IT :Deciphered
Exercise(Due April 11 )
The Alphabet Encoding:
The Message:
CAB
Find an appropriate
and then
Encode
Encipher Decipher
the message.
Definitions:
Given a prime, , we are looking at , the multiplicative group of non-zero elements in .
We say is primitive root if for .
An an example is but not
Given a primitive root , for any define the discrete logarithm of written , to be the least positive integer such that
Note
Methodology:
Given
a primitive root, choose a private key
.
To allow anybody to securely transmit messages to you:
Tell the world and, . Assume somebody wants to send the message to you privately, tell them to select a private key compute
and
,
and transmit both values.
To decode the message received:
Compute
To break
the code:
Plan A: You know and, just compute .
Plan B: You
know
and,
just compute
and
since you know
compute
then
compute
In both cases you need to be able to compute the discrete logarithm of a number. Again this is hard computationally.
This image is from Cryptography: Theory And Practice By Douglas Robert Stinson,
an excellent book for those who wish to pursue this subject further.