2/16/2019

Outline
Cryptography
 Traditional cryptography, statistical attacks, Secret-
key encryption, Public-key encryption
RSA cryptosystem (§10.2.3)
 Euler’s theorem, Algorithms for RSA
 Modular power, Modular inverse
Rabin and ElGamal public key algorithms

2/16/2019 2
2/16/2019
 Traditional Cryptography
Ciphers were already studied in ancient times
Caesar’s cipher:
 replace a with d
 replace b with e
 ...
 replace z with c
Caesar’s cipher is an example of a monoalphabetic substitution
cipher, which permutes the characters
Armed with simple statistical knowledge, one can easily break a
monoalphabetic substitution cipher
 most frequent letters in English: e, t, o, a, n, i, ...
 most frequent digrams: th, in, er, re, an, ...
 most frequent trigrams: the, ing, and, ion, ...
The first description of the frequency analysis attack appears in a
book written in the 9th century by the Arab philosopher al-Kindi
2/16/2019 4
 Statistical Attacks
Armed with statistical knowledge about the plaintext language, one
can easily break a monoalphabetic substitution cipher
 Most frequent characters in English: e, t, o, a, n, i, ...
 Most frequent digrams: th, in, er, re, an, ...
 Most frequent trigrams: the, ing, and, ion, ...
The first description of the frequency analysis attack appears in a
book written in the 9th century by the Arab philosopher al-Kindi
Example (S. Singh, The Code Book, 1999):
PCQ VMJYPD LBYK LYSO KBXBJXWXV BXV ZCJPO EYPD
KBXBJYUXJ LBJOO KCPK. CP LBO LBCMKXPV XPV IYJKL PYDBL,
QBOP KBO BXV OPVOV LBO LXRO CI SX'XJMI, KBO JCKO XPV
EYKKOV LBO DJCMPV ZOICJO BYS, KXUYPD: “DJOXL EYPD, ICJ X
LBCMKXPV XPV CPO PYDBLK Y BXNO ZOOP JOACMPLYPD LC UCM
LBO IXZROK CI FXKL XDOK XPV LBO RODOPVK CI XPAYOPL EYPDK.
SXU Y SXEO KC ZCRV XK LC AJXNO X IXNCMJ CI UCMJ SXGOKLU?”
OFYRCDMO, LXROK IJCS LBO LBCMKXPV XPV CPO PYDBLK

2/16/2019 5
 Frequency Analysis
We identify the most common characters, digrams and trigrams in
the ciphertext
Example
PCQ VMJYPD LBYK LYSO KBXBJXWXV BXV ZCJPO EYPD
KBXBJYUXJ LBJOO KCPK. CP LBO LBCMKXPV XPV IYJKL
PYDBL, QBOP KBO BXV OPVOV LBO LXRO CI SX'XJMI, KBO
JCKO XPV EYKKOV LBO DJCMPV ZOICJO BYS, KXUYPD:
“DJOXL EYPD, ICJ X LBCMKXPV XPV CPO PYDBLK Y BXNO
ZOOP JOACMPLYPD LC UCM LBO IXZROK CI FXKL XDOK
XPV LBO RODOPVK CI XPAYOPL EYPDK. SXU Y SXEO KC
ZCRV XK LC AJXNO X IXNCMJ CI UCMJ SXGOKLU?”
OFYRCDMO, LXROK IJCS LBO LBCMKXPV XPV CPO
PYDBLK
First guess:
 LBO is THE

2/16/2019 6
 Decryption
Code:
X Z A V O I D B Y G E R S P C F H J K L M N Q T U W
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Ciphertext:
PCQ VMJYPD LBYK LYSO KBXBJXWXV BXV ZCJPO EYPD
KBXBJYUXJ LBJOO KCPK. CP LBO LBCMKXPV XPV IYJKL PYDBL,
QBOP KBO BXV OPVOV LBO LXRO CI SX'XJMI, KBO JCKO XPV
EYKKOV LBO DJCMPV ZOICJO BYS, KXUYPD: “DJOXL EYPD, ICJ X
LBCMKXPV XPV CPO PYDBLK Y BXNO ZOOP JOACMPLYPD LC
UCM LBO IXZROK CI FXKL XDOK XPV LBO RODOPVK CI XPAYOPL
EYPDK. SXU Y SXEO KC ZCRV XK LC AJXNO X IXNCMJ CI UCMJ
SXGOKLU?”
OFYRCDMO, LXROK IJCS LBO LBCMKXPV XPV CPO PYDBLK
Plaintext:
Now during this time Shahrazad had borne King Shahriyar three sons.
On the thousand and first night, when she had ended the tale of Ma'aruf,
she rose and kissed the ground before him, saying: “Great King, for a
thousand and one nights I have been recounting to you the fables of past
ages and the legends of ancient kings. May I make so bold as to crave a
favour of your majesty?”
Epilogue, Tales from the Thousand and One Nights
2/16/2019 7
 Secret-Key Encryption
A secret-key cipher uses a unique key K to encrypt and decrypt
Caesar’s generalized cipher uses the modular addition of each
character (viewed as an integer) with the key:
C[i]P[i]K mod m
P[i]C[i] K mod m
More secure secret-key encryption schemes have been devised
in this century
Examples:
 DES
 3DES
 IDEA
 BLOWFISH
With private-key encryption, a distinct secret key must be
established for every pair of parties

2/16/2019 8
2/16/2019
 Public-Key Encryption
The concept of Public –key was invented by Whitfield
D and Martin Hellmann in 1970.
The first public-key algorithm was DES (Data
encryption Standard, I was a standard for 15 years.
Schemes:
 RSA

 Rabin

 El Gamal

 Knapsack

2/16/2019 10
2/16/2019
 Outline
Euler’s theorem (§10.1.3)
RSA cryptosystem (§10.2.3)
 Definition
 Example
 Security
 Correctness
Algorithms for RSA
 Modular power (§10.1.4)
 Modular inverse (§10.1.5)
 Randomized primality testing (§10.1.6)

2/16/2019 12
 Euler’s Theorem
The multiplicative group for Zn, denoted with Z*n, is the subset of
elements of Zn relatively prime with n
The totient function of n, denoted with (n), is the size of Z*n
Example
Z*10  { 1, 3, 7, 9 } (10) 4
If p is prime, we have
Z*p  {1, 2, …, (p1)} (p)  p1
Euler’s Theorem
For each element x of Z*n, we have x(n) mod n  1
Example (n  10)
3(10) mod 10 34 mod 10 81 mod 10 1
7(10) mod 10 74 mod 10 2401 mod 10 1
9(10) mod 10 94 mod 10 6561 mod 10 1

2/16/2019 13
 RSA Cryptosystem
Setup: Example
 npq, with p and q  Setup:
primes  p7, q17
 e relatively prime to  n717119
(n)(p  1) (q  1)  (n)61696
 d inverse of e in Z(n)  e5
Keys:  d77
 Public key: KE(n, e)  Keys:
 Private key: KDd
 public key: (119, 5)
 private key: 77
Encryption:
 Encryption:
 Plaintext M in Zn  M19
e
 C = M mod n
 C195 mod 119 = 66
Decryption:  Decryption:
 M = Cd mod n  C6677 mod 119 = 19
2/16/2019 14
 Complete RSA Example
Setup: Encryption
 p5, q11  CM3 mod 55
 n51155 Decryption
 (n)41040  MC27 mod 55
 e3

 d2732781 240 + 1)

M 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
C 1 8 27 9 15 51 13 17 14 10 11 23 52 49 20 26 18 2
M 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
C 39 25 21 33 12 19 5 31 48 7 24 50 36 43 22 34 30 16
M 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
C 53 37 29 35 6 3 32 44 45 41 38 42 4 40 46 28 47 54

2/16/2019 15
2/16/2019
 Correctness
We show the correctness of Thus, we obtain
the RSA cryptosystem for the (Me)d mod n 
case when the plaintext M Med mod n 
does not divide n Mk(n)1 mod n MMk(n)
Namely, we show that mod n 
(Me)d mod n  M M (M(n))k mod n 
Since ed mod (n)1, there is M (M(n) mod n)k mod n 
an integer k such that M (1)k mod n 
ed  k(n)1 M mod n 
Since M does not divide n, by M
Euler’s theorem we have See the book for the proof of
correctness in the case when
M(n) mod n 1 the plaintext M divides n

2/16/2019 17
 Algorithmic Issues
The implementation of Setup
the RSA cryptosystem Generation of random
requires various numbers with a given
algorithms number of bits (to generate
candidates p and q)
Overall Primality testing (to check
 Representation of integers that candidates p and q are
of arbitrarily large size and prime)
arithmetic operations on Computation of the GCD (to
them verify that e and (n) are
Encryption relatively prime)
 Modular power Computation of the
multiplicative inverse (to
Decryption compute d from e)
 Modular power

2/16/2019 18
2/16/2019
 Modular Inverse
Theorem Given positive integers a and b,
Given positive integers a the extended Euclid’s algorithm
and b, let d be the smallest computes a triplet (d,i,j) such that
positive integer such that  dgcd(a,b)
dia + jb  dia + jb
for some integers i and j. To test the existence of and
We have compute the inverse of x  Zn, we
execute the extended Euclid’s
dgcd(a,b) algorithm on the input pair (x,n)
Example Let (d,i,j) be the triplet returned
 a21 dix + jn
 b15 Case 1: d1
 d3
i is the inverse of x in Zn
 i3, j4
Case 2: d1
 3321 + (4)15 
6360 3 x has no inverse in Zn
2/16/2019 20
 Pseudoprimality Testing
The number of primes less than or equal to n is about n ln n
Thus, we expect to find a prime among, O(b) randomly generated
numbers with b bits each
Testing whether a number is prime (primality testing) is believed
to be a hard problem
An integer n 2 is said to be a base-x pseudoprime if
 xn 1 mod n1 (Fermat’s little theorem)
Composite base-x pseudoprimes are rare:
 A random 100-bit integer is a composite base-2 pseudoprime with
probability less than 10-13
 The smallest composite base-2 pseudoprime is 341
Base-x pseudoprimality testing for an integer n:
 Check whether xn 1 mod n1
 Can be performed efficiently with the repeated squaring algorithm
2/16/2019 21
 Randomized Primality Testing
Compositeness witness function
witness(x, n) with error probability Algorithm RandPrimeTest(n, k)
q for a random variable x Input integer n,confidence
Case 1: n is prime parameter k and composite
witness function witness(x,n)
witness w(x, n)false with error probability q
Case 2: n is composite Output an indication of
witness w(x, n)false with whether n is composite or prime
probability q1 with probability 2k
Algorithm RandPrimeTest tests
whether n is prime by repeatedly t  klog2(1q)
evaluating witness(x, n) for i  1 to t
A variation of base- x x  random()
pseudoprimality provides a if witness(x,n)= true
suitable compositeness witness return “n is
function for randomized primality composite”
testing (Rabin-Miller algorithm) return “n is prime”
2/16/2019 22
 Rabin and ElGamal
public-key encryption

(Examples)

2/16/2019 23
 Rabin public-key encryption
Rabin encryption is an extremely fast operation as it only involves a single modular
squaring. By comparison with RSA.
Rabin encryption is slower than encryption but is comparable in speed to RSA
decryption
How it works if B wants to send a message to A?
Generation key: Each entity generate create a public key and corresponding private
key
1. Generate 2 large random numbers primes p an q, each with the same size
2. Compute n=pq
3. The public key is n and the private key is p and q
The encryption:
1. Represent the message as an integer m in the range {0,1,….,n-1}
2. Compute c=m2modn
3. Send the cipher text c to A
The Decryption:
1. Find the square roots m1,m2,m3 and m4 of c modulo n2
2. The message sent was either m1,m2,m3 or m4.

2/16/2019 24
 Rabin public key- Example
Key generation: A choose the primes p=277, q=331, and computes n=pq=91687. A’s publi
key is n=91687, while A’s private key is p=277 and q=331
Encryption: Suppose that the last six bits of the original messages are required to b
replied prior to encryption. In order to encrypt the 10-bits message m=1001111001,
replies the last six bits of m to obtain 16-bits message.
m=1000111001111001 which in decimal notation is m=40569, the computes:

C=m2modn = 405692 mod 91687 = 62111

And sent this to A

Decryption: to decrypt c, A use the square root algorithm to know the factors of
to compute the four square root of c mod n

m1=69954, m2=22033, m3=40569, m45118

m1=1000100000010110, m2=101011000010001,
m3=1001111001111001, m4=110001111010110.

2/16/2019 25
ElGamal public-key encryption
Is bases on the difficulty of the problem called" discrete algorithm”
How it works if B wants to send a message to A?
Key generation:
Each entity generate create a public key of the multiplicative group
1. Generate a large random prime p and generator α of the multiplicative group
Z p* of the integers modulo p.
2. Select a random integer a, between 1 and p-2 and compute αa mod p
3. A’s public key is (p,α, αa ); A’s private key is a
Encryption: B should b the following:
1. Obtain A’s authentication public key (p,α, αa );
2. Represent the message as an integer m in the range of {0,1,2…p-1}
3. Select a random integer k, between 1 and p-2
4. Compute γ = αk mod p and ζ = m.(αa)k mod p
5. Send the cipher text c=(γ, ζ ) to A
Decryption: Recover plaintext m from c, A should do the following:
1. Use the private key a to compute γ p-1-a mod p
2. Recover m by computing (γ -a ). ζ mod p

2/16/2019 26
 ElGamal- Example
Key generation: A select the primes p=2357 and generate α=2 of Z * . A chooses the
2357
private key a=1751 and computes:
αa mod p=2 1751 mod 2357 =1185
A’s public key is (p=2357, α=2, αa =1185)

Encryption: To encrypt the message m=2035, B selects a random integer k=1520 and
computes:
γ = 21520 mod 2357=1430
ζ = 2035 . 11851520. mod 2357 = 697

B sends γ = 1430 and ζ = 697 to A

Decryption: to decrypt c, A computes:

γ p-1-a = 1435605 mod 2357 = 872

and recover m by computing
m = 872.697 mod 2357 m= 2035
2/16/2019 27
 Conclusions
Fundaments of theory of cryptography and several powerful
algorithms to protect the data integrity, authenticating,
authorization and confidentiality were discussed during this
presentation.

A variety of cryptographic techniques have been developed to

support the communications an insecure network. The goal of
this presentation is present the Fundaments of theory of
cryptography and several powerful algorithms to protect the data
integrity, authenticating, authorization and confidentiality .

2/16/2019 28