Information Theory

exercise in the previous class
Decrypt the following ciphertext.
qiw aufmlyn gcmwz yz c mcxae yoqweocqyaocu wpwoq jwcqkeyog zkmmwe
cod vyoqwe zlaeqz, yo viyni qiakzcodz aj cqiuwqwz lceqynylcqw yo c pceywqf
aj namlwqyqyaoz. qiw aufmlyn gcmwz icpw namw qa hw ewgcedwd cz qiw
vaeud'z jaewmazq zlaeqz namlwqyqyao viwew maew qico qva ikodewd
ocqyaoz lceqynylcqw. qiw gcmwz cew nkeewoquf iwud wpwef qva fwcez, vyqi
zkmmwe cod vyoqwe aufmlyn gcmwz cuqweocqyog, cuqiakgi qiwf annke
wpwef jake fwcez vyqiyo qiwye ewzlwnqypw zwczaocu gcmwz.
hint: find “typical patterns” of English
1
exercise in the previous class: solution
use the JAVA applet at;
http://apal.naist.jp/~kaji/crypto/Substitution.html
The Olympic Games is a major international event featuring
summer and winter sports, in which thousands of athletes
participate in a variety of competitions. The Olympic Games have
come to be regarded as the world's foremost sports competition
where more than two hundred nations participate. The Games
are currently held every two years, with Summer and Winter
Olympic Games alternating, although they occur every four years
within their respective seasonal games.
2
previous class: common-key cryptography
symmetric-key ―, classic ―, ...
the encryption and decryption use the same key
the sender and the receiver need to agree the key in advance
sender
receiver
key agreement
secure channel,
or secure protocol
A
encrypt
B
decrypt
3
today: public-key cryptography
public-key cryptography
the receiver of ciphertexts prepares a pair of keys
the encryption key and the decryption key
the encryption key is opened to the public
the decryption key is kept secretly by the receiver
sender
receiver
send in advance
open channel
A
encrypt
B
decrypt
4
the difference of the two cryptography
common-key cryptography = vault (金庫)
A
B
key needed
key needed
public-key cryptography = post (郵便受け)
A
B
key NOT needed
key needed
each individual has its own “post”
C
D
5
public-key cryptography
a public-key cryptography is a triple of algorithms (G, E, D)
G(seed); generates a pair of keys ek and dk
E(ek, m); encrypts m by using ek as an encryption key
D(dk, c); decrypts c by using dk as an decryption key
If (ek, dk)  G, then D(dk, E(ek, m)) = m.
If (ek, dk)  G, then D(dk, E(ek, m))  m.
G
ek
m
E
seed
dk
c
D
m
6
key management
Each user needs to generate his/her own key pair (ek, dk).
The decryption key dk is kept secretly.
 only the legitimate (本物の) user can do decryption
The encryption key ek is opened to the public.
 anybody can do encryption
D
A dk
A
B dk
B
C dk
C
ekA
ekB
ekC
A...ekA
B...ekB
C...ekC
7
RSA cryptography
proposed by Rivest, Shamir and Adelman in 1977
keys, plaintexts and ciphertexts are integers
encryption:
key is a pair of integers: e & n
c = me mod n
decryption:
key is a pair of integers: d & n
m = cd mod n
the “trick” is in the choice of e, d and n
keys must be very long ... n  1024bits
S
R
R
A
S
A
8
numerical example
e = 3, d = 7, n = 33:
m
c = m3 mod 33
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
1
8
27
31
26
18
13
17
3
10
11
12
19
5
9
4
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
c
29
24
28
14
21
22
23
30
16
20
15
7
2
6
25
32
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
m = c7 mod 33
1
29
9
16
14
30
28
2
15
10
11
12
7
20
27
25
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
8
6
13
26
21
22
23
18
31
5
3
19
17
24
4
32
9
what did we do?
encryption & decryption: (m3 mod 33)7 mod 33  m21 mod 33
m
m2
1
2
3
4
5
6
7
8
9
10
11
1
4
9
16
25
3
16
31
15
1
22
m3
m3
m4
1
8
27
31
26
18
13
17
3
10
11
1
16
15
25
31
9
25
4
27
1
22
m5 m6
1
32
12
1
23
21
10
32
12
10
11
1
31
3
4
16
27
4
25
9
1
22
m3
(m3)7
How can we choose such numbers?
m16 m17 m18 m19 m20
1
31
3
4
16
27
4
25
9
1
22
1
29
9
16
14
30
28
2
15
10
11
m3
1
25
27
31
4
15
31
16
3
1
22
1
17
15
25
20
24
19
29
27
10
11
m21
1 1
1 2
12 3
1 4
1 5
12 6
1 7
1 8
12 9
1 10
22 11
m3
10
key generation of RSA
How to choose e, d and n of the key of RSA:
step 1: choose two prime integers p and q, and let n = pq
step 2: choose e which is coprime (互いに素) with (p – 1)(q – 1)
step 3: determine d such that ed  1 mod (p – 1)(q – 1)
e, n ... opened to the public
d (, p, q) ... kept secretly
p=3
q = 11
(p – 1)(q – 1) = 20
e=3
a and b are coprime if gcd(a, b) = 1
a  b mod c  (a mod c) = (b mod c)
d=7
n = 33
key
11
algorithmic details
Q1: How can we generate prime numbers?
A1: Generate numbers randomly, and do “primality tests”.
Q2: How can we find d such that ed  1 mod (p – 1)(q – 1)?
A2: Use the Euclidian algorithm for computing a gcd.
a0
ai
ai+1 = bi
gcd of a0 and b0
aj
b0
bi
bi+1 = ai mod bi
bj = 0
12
computation of d with the Euclidian Algorithm++
Use the Euclidian algorithm for  = (p – 1)(q – 1) and e.
b0 = e
a0 = 
a1 = e
b1 = a0 mod b0 = a0 – k1b0
=  – k1e
a2 = b1
b2 = a1 mod b1 = a1 – k2b1
= – k2 + (k1+1)e
bi = xi + yie
aj=1
bj–1= 1
bj = 0
because
 and e are coprime
1 = x + ye
ye = –x + 1
ye  1 mod 
choose d = y mod 
13
example of the computation of d
assume  = 130 and e = 59
130
59
59
12
= 130 – 2×59
12
11
= 59 – 4×12 = – 4×130 + 9×59
11
1
= 12 – 11 = 5×130 – 11×59
1 = x + ye
1 = 5 + (–11)e
ye = –x + 1
(–11)e = –5 + 1
ye  1 mod 
(–11)e  1 mod 
d = –11 mod 130 = 119
ed = 59×119=7021
= 54×130 +1
ed  1 mod 
14
encryption & decryption
encryption key: e and n
decryption key: d (and n)
plaintexts & ciphertexts ... integers in {0, ..., n – 1}
encryption: c = me mod n
decryption: m = cd mod n
modulus exponential?
... see the page 25 of the slide of the previous class
15
summarizing example: key generation of RSA
step 1: choose p = 79, q = 97, and we have n = pq = 7663
step 2: choose e = 5, which is coprime with (p – 1)(q – 1) = 7488
step 3: determine d with 5d  1 mod 7488 as follows:
7488
5
5
3 = 7488 – 1497×5
3
2 = 5 – 3 = –7488 + 1498×5
2
1 = 3 – 2 = 2×7488 – 2995×5
d = – 2995 mod 7488 = 4493
all computation in
mod (p – 1)(q – 1)
16
summarizing example: encryption & decryption
keys: e = 5, d = 4493, n = 7663
encryption:
c = m5 mod 7663
decryption:
m = c4493 mod 7663
= c4096c256c128c8c4c mod 7663
all computation in
mod n = pq
m
m^2
m^4
m^5
51
2601
6435
6339
c
c^2
c^4
c^8
c^16
c^32
c^64
c^128
c^256
c^512
c^1024
c^2048
c^4096
c^4493
6339
5812
840
604
4655
5724
4851
6791
1747
2135
6403
1359
98
51
17
the soundness proof of RSA: preparation
We need to show that
(me mod n)d mod n = med mod n = m.
two assisting lemmas...
Fermat’s little theorem:
xp–1  1 mod p for a prime number p and any x with gcd(x, p) = 1
Corollary of Chinese Remainder Theorem[孫子算経]:
If x  a mod p and x  a mod q, then x  a mod pq,
where p and q are different prime numbers.
18
the soundness proof of RSA
Theorem: med mod n = m.
Proof:
ed  1 mod (p – 1)(q – 1) implies that ed = k(p – 1)(q – 1) + 1
we have med  m mod p, because...
if gcd(m, p) = 1, then mp–1  1 mod p by Fermat, and
med = (mp–1)k(q–1)m  m mod p.
if gcd(m, p)≠ 1, then m is a multiple of p and both sides  0
similarly we have med  m mod q
the corollary of the Chinese Remainder Theorem guarantees
that med mod n = m
19
attacks on RSA
given an encryption key e and n, and a ciphertext c,
can we find the plaintext m with c = me mod n?
exhaustive attack
an attacker can “encrypt” a plaintext
test if c = xe mod n for all x{0, ..., n – 1}
choose n large, and this attack is not serious
e
n
c
m?
computing the e-th root of c in mod n
computing the e-th root is easy for real numbers
the algorithms do not work for the discrete “mod n” world
20
attacks on RSA: factorization of n
factoring (素因数分解) attack
find prime numbers p and q with n = pq
once p and q are revealed, d can be determined uniquely
use d to decrypt c
But, can we factor n?
there are several algorithms for factoring
brute force, quadratic sieve, elliptic curve
it is still difficult to factor large composite numbers
n should be chosen so that it is in 1,024 bits or more
You may come up with a good idea tomorrow!
21
the factoring and RSA
“if we can factor a given n, then we can break RSA”
 breaking RSA is not more difficult than factoring
breaking RSA
factoring
easy
difficult
breaking Rabin cipher
theoretically saying, there are more favorable cryptography...
Rabin cipher:
if we can factor a given n, then we can break Rabin cipher
if we can break Rabin cipher, then we can factor a given n
“breaking Rabin cipher is as difficult as factoring”
(Rabin is not efficient and not practical, many people consider...)
22
the security of RSA
the security of RSA is NOT a mathematically proved fact...
many people believes that it is difficult to break RSA
there can be somebody who knows a good algorithm and
is decrypting RSA silently...
no backup from the theory of computational complexity
breaking RSA NP, but not clear if NP-complete or not
a quantum computer can break RSA
Shor’s quantum algorithm for factoring
23
ElGamal encryption: key generation
based on the discrete logarithm problem (DLP)
probabilistic encryption: one plaintext has many ciphertexts
key generation (remind the Diffie-Hellman key agreement)
choose a prime number q and a generator g of Fq
choose a random x, and compute y = gx mod q
the encryption key is q, g and y
the decryption key is x
24
ElGamal: encryption & decryption
encryption of m:
choose random r, and let
c1 = gr mod q
c2 = m + yr mod q
(c1, c2) is the ciphertext
r
g
y
m
mod q
decryption of (c1, c2):
compute u = c1x mod q
compute v = c2 – u mod q
v is the plaintext
c1
x
(gx)r
+
c1x
(gr)x
c2
mod q
-
m
25
ElGamal: example
Choose q = 13 and g = 7
1  712 mod 13, 2  711 mod 13, ..., 12  76 mod 13
Choose x = 5 and determine y = 75 =16807  11 mod 13
encryption: m = 6, r = 3
c1 = 73 = 343  5 mod 13, c2 = 6 + 113 =1337  11 mod 13
c = (5, 11) is the ciphertext
decryption: c = (5, 11)
u = 55 =3125  5 mod 13, v = 11 – 5  6 mod 13
v = 6 is the plaintext
26
probabilistic encryption
the encryption uses a random r together with a plaintext m
different choices of r make different ciphertexts
 the exhaustive attack is “more difficult”
c0
c1
m
m
c
m
m
RSA
cq–1
ElGamal
c = (c1, c2) ... c1 is needed to cancel the effect of r at decryption
 the ciphertext is “longer” in length
“breaking ElGamal is not more difficult than solving DLP”
27
public-key vs. common-key
common-key cryptography
more efficient: computational cost, key length, ...
more variations: many algorithms, many alternatives, ...
key-agreement is difficult and costly
public-key cryptography
“key-agreement” is replaces by lighter “key-distribution”
(public encryption keys must be delivered correctly)
hybrid use of public and common-key cryptography is common
use RSA to deliver the key of AES, for example
28
summary of chapter 4
We studied very basics of cryptography.
common-key cryptography
DES and AES
key-agreement protocol
public-key cryptography
algorithms and theory of RSA
ElGamal encryption
29
summary of this course
chapter 1: measuring information
chapter 2: compact representation of information
chapter 3: coding for noisy communication
chapter 4: cryptography
Information theory turns information processing from
“ad-hoc handicrafts” to “well-defined theory”.
The study is so fundamental that usual people do not notice,
but professionals of information must know it.
30
about test
June 4(Mon), 9:20AM, exercise
June 5 (Tue), 9:20AM, this room
you can bring books, notes and copies of slides
you can bring a calculator and/or PC
PC must be disconnected from the network:
download all needed material before the test starts
本，ノート，資料，電卓，PC ...なんでも持ちこみ可
PC 等の通信機能は使用不可
必要な資料類は事前にダウンロードしておくこと
31

Download Report