· the public-key is easily computed from the private key and other information about the

cipher (a polynomial time (P-time) problem)

· however, knowing the public-key and public description of the cipher, it is still
computationally infeasible to compute the private key (an NP-time problem)
· thus the public-key may be distributed to anyone wishing to communicate securly with its
owner (although secure distribution of the public-key is a non-trivial problem - the key distribution
problem)
· have three important classes of public-key algorithms:
o Public-Key Distribution Schemes (PKDS) - where the scheme is used to securely
exchange a single piece of information (whose value depends on the two parties, but cannot be set).
o This value is normally used as a session key for a private-key scheme
o Signature Schemes - used to create a digital signature only, where the private-key
signs (create) signatures, and the public-key verifies signatures
o Public Key Schemes (PKS) - used for encryption, where the public-key encrypts
messages, and the private-key decrypts messages.
o Any public-key scheme can be used as a PKDS, just by selecting a message which is
the required session key
o Many public-key schemes are also signature schemes (provided encryption&
decryption can be done in either order)

RSA Public-Key Cryptosystem

· best known and widely regarded as most practical public-key scheme was proposed by
Rivest, Shamir & Adleman in 1977:
R L Rivest, A Shamir, L Adleman, "On Digital Signatures and Public Key Cryptosystems",
Communications of the ACM, vol 21 no 2, pp120-126, Feb 1978
· it is a public-key scheme which may be used for encrypting messages, exchanging keys, and
creating digital signatures
· is based on exponentiation in a finite (Galois) field over integers modulo a prime
o nb exponentiation takes O((log n)3) operations
· its security relies on the difficulty of calculating factors of large numbers
o nb factorization takes O(e log n log log n) operations
o (same as for discrete logarithms)
· the algorithm is patented in North America (although algorithms cannot be patented
elsewhere in the world)
o this is a source of legal difficulties in using the scheme
· RSA is a public key encryption algorithm based on exponentiation using modular arithmetic
· to use the scheme, first generate keys:
· Key-Generation by each user consists of:
o selecting two large primes at random (~100 digit), p, q
o calculating the system modulus R=p.q p, q primes
o selecting at random the encryption key e,
o e < R, gcd(e, F(R)) = 1
o solving the congruence to find the decryption key d,
o e.d [[equivalence]] 1 mod [[phi]](R) 0 <= d <= R
o publishing the public encryption key: K1={e,R}
o securing the private decryption key: K2={d,p,q}
· Encryption of a message M to obtain ciphertext C is:
· C = Me mod R 0 <= d <= R
· Decryption of a ciphertext C to recover the message M is:
o M = Cd = Me.d = M1+n.[[phi]](R) = M mod R
· the RSA system is based on the following result:
if R = pq where p, q are distinct large primes then
X [[phi]](R) = 1 mod R
for all x not divisible by p or q
and [[Phi]](R) = (p-1)(q-1)
RSA Example
· usually the encryption key e is a small number, which must be relatively prime to [[phi]](R)
(ie GCD(e, [[phi]](R)) = 1)
· typically e may be the same for all users (provided certain precautions are taken), 3 is
suggested
· the decryption key d is found by solving the congruence:
e.d [[equivalence]] 1 mod [[phi]](R), 0 <= d <= R,
· an extended Euclid's GCD or Binary GCD calculation is done to do this.
given e=3, R=11*47=517, [[phi]](R)=10*46=460
then d=Inverse(3,460) by Euclid's alg:
i y g u v
0 - 460 1 0
1 - 3 0 1
 2 153 1 1 -153
3 3 0 -3 460
ie: d = -153, or 307 mod 517
· a sample RSA encryption/decryption calculation is:
M = 26
C = 263 mod 517 = 515
M = 515307 mod 517 = 26
·

Security of RSA
· The security of the RSA scheme rests on the difficulty of factoring the modulus of the
scheme R
· best known factorization algorithm (Brent-Pollard) takes:

operations on number R whose largest prime factor is p

Decimal Digits in R #Bit Operations to Factor R

20 7200
40 3.11e+06
60 4.63e+08
80 3.72e+10
100 1.97e+12
120 7.69e+13
140 2.35e+15
160 5.92e+16
180 1.26e+18
200 2.36e+19

· This leads to R having a length of 200 digits (or 600 bits) given that modern computers
perform 1-100 MIPS the above can be divided by 106 to get a time in seconds
o nb: currently 1e+14 operations is regarded as a limit for computational feasability
and there are 3e+13 usec/year
· but most (all!!) computers can't directly handle numbers larger than 32-bits (64-bits on the
very newest)
· hence need to use multiple precision arithmetic libraries to handle numbers this large
Multi-Precision Arithmetic
· involves libraries of functions that work on multiword (multiple precision) numbers
· classic references are in Knuth vol 2 - "Seminumerical Algorithms"
o multiplication digit by digit
o do exponentiation using square and multiply[6]
· are a number of well known multiple precision libraries available - so don't reinvent the
wheel!!!!
· can use special tricks when doing modulo arithmetic, especially with the modulo reductions
Faster Modulo Reduction
* Chivers (1984) noted a fast way of performing modulo reductions whilst doing multi-precision
arithmetic calcs

Given an integer A of n characters (a0, ... , an-1) of base b

then

ie: this implies that the MSD of a number can be removed and its remainder mod m added to the
remaining digits will result in a number that is congruent mod m to the original.
* Chivers algorithm for reducing a number is thus:
1. Construct an array R = (bd, 2.bd, ... , (b-1).bd)(mod m)
2. FOR i = n-1 to d do
WHILE A[i] != 0 do
j = A[i];
A[i] = 0;
A = A + bi-d.R[j];
END WHILE
END FOR
where A[i] is the ith character of number A
R[j] is the jth integer residue from the array R
n is the number of symbols in A
d is the number of symbols in the modulus
Speeding up RSA - Alternate Multiplication Techniques
· conventional multiplication takes O(n2) bit operations, faster techniques include:
· the Schonhage-Strassen Integer Multiplication Algorithm:
o breaks each integer into blocks, and uses them as coefficients of a polynomial
o evaluates these polynomials at suitable points, & multiplies the resultant values
o interpolates these values to form the coefficients of the product polynomial
o combines the coefficients to form the product of the original integer
o the Discrete Fourier Transform, and the Convolution Theorem are used to speed up
the interpolation stage
o can multiply in O(n log n) bit operations
· the use of specialized hardware because:
o conventional arithmetic units don't scale up, due to carry propogation delays
o so can use serial-parallel carry-save, or delayed carry-save techniques with O(n)
gates to multiply in O(n) bit operations,
o or can use parallel-parallel techniques with O(n2) gates to multiply in O(log n) bit
operations

RSA and the Chinese Remainder Theorem

· a significant improvement in decryption speed for RSA can be obtained by using the
Chinese Remainder theorem to work modulo p and q respectively
o since p,q are only half the size of R=p.q and thus the arithmetic is much faster
· CRT is used in RSA by creating two equations from the decryption calculation:
M = Cd mod R
as follows:

M1 = M mod p = (C mod p)d mod (p-1)

M2 = M mod q = (C mod q)d mod (q-1)
then the pair of equations

M = M1 mod p M = M2 mod q
has a unique solution by the CRT, given by:

M = [((M2 +q - M1)u mod q] p + M1

where

p.u mod q = 1
Primality Testing and RSA
· The first stage of key-generation for RSA involves finding two large primes p, q
· Because of the size of numbers used, must find primes by trial and error
· Modern primality tests utilize properties of primes eg:
o an-1 = 1 mod n where GCD(a,n)=1
o all primes numbers 'n' will satisfy this equation
o some composite numbers will also satisfy the equation, and are called pseudo-
primes.
· Most modern tests guess at a prime number 'n', then take a large number (eg 100) of
numbers 'a', and apply this test to each. If it fails the number is composite, otherwise it is is
probably prime.
· There are a number of stronger tests which will accept fewer composites as prime than the
above test. eg:

RSA Implementation in Practice

· Software implementations
o generally perform at 1-10 bits/second on block sizes of 256-512 bits
o two main types of implementations:
§ - on micros as part of a key exchange mechanism in a hybrid scheme
§ - on larger machines as components of a secure mail system
· Harware Implementations
o generally perform 100-10000 bits/sec on blocks sizes of 256-512 bits
o all known implementations are large bit length conventional ALU units

ElGamal
· A variant of the Diffie-Hellman key distribution scheme, allowing secure exchange of
messages
· published in 1985 by ElGamal in
T. ElGamal, "A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms",
IEEE Trans. Information Theory, vol IT-31(4), pp469-472, July 1985.
· like Diffie-Hellman its security depends on the difficulty of factoring logarithms
· Key Generation
o select a large prime p (~200 digit), and
o [[alpha]] a primitive element mod p
o A has a secret number xA
o B has a secret number xB
o A and B compute yA and yB respectively, which are then made public
§ yA = [[alpha]]xA mod p
§ yB = [[alpha]]xB mod p
· to encrypt a message M into ciphertext C,
o selects a random number k, 0 <= k <= p-1
o computes the message key K
§ K = yBk mod p
o computes the ciphertext pair: C = {c1,c2}
§ C1 = [[alpha]]k mod p C2 = K.M mod p
· to decrypt the message
o extracts the message key K
§ K = C1xB mod p = [[alpha]]k.xB mod p
o extracts M by solving for M in the following equation:
§ C2 = K.M mod p
Other Public-Key Schemes
· a number of other public-key schemes have been proposed, some of the better known being:
o Knapsack based schemes
o McEleice's Error Correcting Code based schems
· ALL of these schemes have been broken
· the only currently known secure public key schemes are those based on exponentiation
(all of which are patented in North America)
· it has proved to be very difficult to develop secure public key schemes
· this in part is why they have not been adopted faster, as their theorectical advantages might
have suggested
AUTHENTICATION REQUIREMENTS
In the context of communication across a network, the following attacks can be identified:
Disclosure – releases of message contents to any person or process not possessing the
appropriate cryptographic key.
Traffic analysis – discovery of the pattern of traffic between parties.
Masquerade – insertion of messages into the network fraudulent source.
Content modification – changes to the content of the message, including
insertion deletion, transposition and modification.
Sequence modification – any modification to a sequence of messages between parties,
including insertion, deletion and reordering.
Timing modification – delay or replay of messages.

Source repudiation – denial of transmission of message by source.

Destination repudiation – denial of transmission of message by destination.
easures to deal with first two attacks are in the realm of message confidentiality. Measures to deal
with 3 through 6 are regarded as message authentication. Item 7 comes under digital signature and
dealing with item 8 may require a combination of digital signature and a protocol to counter this
attack.

AUTHENTICATION FUNCTIONS

Any message authentication or digital signature mechanism can be viewed as having fundamentally
two levels. At the lower level, there may be some sort of function that produces an authenticator: a
value to be used to authenticate a message. This lower layer function is then used as primitive in a
higher-layer authentication protocol that enables a receiver to verify the authenticity of a message.
The different types of functions that may be used to produce an authenticator
are as follows:
Message encryption – the cipher text of the entire message serves as its
authenticator.
Message authentication code (MAC) – a public function of the message and a secret
key that produces a fixed length value serves as the authenticator.
Hash function – a public function that maps a message of any length into a fixed length
hash value, which serves as the authenticator.

Message encryption
Message encryption by itself can provide a measure of authentication. The analysis differs
from symmetric and public key encryption schemes.
Suppose the message can be any arbitrary bit pattern. In that case, there is no way to determine
automatically, at the destination whether an incoming message is the ciphertext of a legitimate
message. One solution to this problem is to force the plaintext to have some structure that is easily
recognized but that cannot be replicated without recourse to the encryption function. We could, for
example, append an error detecting code, also known as Frame Check Sequence (FCS) or checksum
to each message before encryption
‘A’ prepares a plaintext message M and then provides this as input to a function F that produces an
FCS. The FCS is appended to M and the entire block is then encrypted. At the destination, B
decrypts the incoming block and treats the result as a message with an appended FCS. B applies the
same function F to attempt to reproduce the FCS. If the calculated FCS is equal to the incoming
FCS, then the message is considered authentic.
In the internal error control, the function F is applied to the plaintext, whereas in external error
control, F is applied to the ciphertext (encrypted message).

MESSAGE AUTHENTICATION CODE (MAC)

An alternative authentication technique involves the use of secret key to generate a small fixed
size block of data, known as cryptographic checksum or MAC that is appended to the message.
This technique assumes that two communication parties say A and B, share a common secret key
‘k’. When A has to send a message to B, it calculates the MAC as a function of the message and the
key.
MAC = CK(M) Where M – input message
C – MAC function
K – Shared secret key

+MAC - Message Authentication Code

The message plus MAC are transmitted to the intended recipient. The recipient performs the same
calculation on the received message, using the shared secret key, to generate a new MAC. The
received MAC is compared to the calculated MAC. If it is equal, then the message is considered
authentic.
A MAC function is similar to encryption. One difference is that MAC algorithm need not be
reversible, as it must for decryption. In general, the MAC function is a many- to-one function.