Simplecrypto.pdf

(41 KB) Pobierz
BME VIK, Vajda, 2003
One-Time Pad
The sender uses each key letter to encrypt exactly one plaintext
character.
Encryption is the addition modulo 26 of the plaintext character and
the
one-time pad key character.
The sender encrypts the message and then destroys the used pages
of the pad or used section of the tape. The receiver has an identical
pad and uses each key on the pad, in turn, to decrypt each letter of
the ciphertext. The receiver destroys the same pad pages or tape
section after decrypting the message.
ONETIMEPAD
and the key sequence from the pad is
TBFRGFARFM
then the ciphertext is
IPKLPSFHGQ
because
O + T mod 26 = I
N + B mod 26 = P
E + F mod 26 = K
etc.
Binary case:
x = 01001101 01011101 ...
k = 11010000 11101011 ...
-----------------------------
y=
10011101 10110110 ...
1
BME VIK, Vajda, 2003
y + k = (x + k) + k = x + (k + k) = x
+ : mod 2 addition (XOR)
Probabilistic model (C. Shannon)
X, Y, K random variable
K has uniform distribution (coin flipping sequence)
X and K are independent
Y
=
E
K
(
X
)
Perfect encryption:
I(X,Y)=0.
Theorem 1:
Perfect encryption exists.
Proof: One time pad
Y=X+K
(+ =
⊕
)
P(Y=y|X=x)= P(X+K=y|X=x)= P(K=y-x|X=x)= P(K=y-x)= 2
-N
(X and K are independent)
P(Y=y) =
Σ
x
P(X+K=y|X=x)P(X=x) = 2
-N
= P(Y=y|X=x)
♦
2
BME VIK, Vajda, 2003
Theorem 2:
H(K)
≥
H(X)
H(X) = H(X|Y) + I(Y;Y) = H(X|Y)
H(X|Y)
≤
H(X,K|Y) = H(K|Y) + H(X|Y,K)
= H(K|Y)
≤
H(K)
( H(U,V) = H(U) + H(V|U), H(X|Y,K)=0 )
♦
Corrollary
: H(X)
≤
H(K) = H(K
1
, K
2
,..., K
N
)
≤
|K|
Use data compession before applying one time pad encryption!
3
BME VIK, Vajda, 2003
Consider the case when |
P
|=|
C
|=|
K
| , i.e. the size of message space,
key space and ciphertext space is the same.
Theorem 3:
Assume |
P
|=|
C
|=|
K
|. The cryptosystem is perfect
if and only if
A1.) every key is used with the same probability (1/|
K
| ), and
A2.) for every message
x
and cipertext
y
there exists a unique
key
k,
such that E
k
(x)=y.
Proof:
1. A1, A2
→
perfect (similar proof as for Th.1.)
2. perfect
→
A1, A2:
perfect
→
for each x,y there exists at least one k such that E
k
(x)=y
|
C
|=|
K
|
→
A2.
fix y
Bayes th.
→
P(x
i
|y) = P(y|x
i
)P(x
i
)/P(y) = P(k
i
)P(x
i
)/P(y)
(E
ki
(x
i
)=y
i
)
perfect
→
P(x
i
|y)=P(x
i
)
→
1=P(k
i
)/P(y)
→
P(k
i
) is constant
→
P(k
i
)= 1/|
K
|.
4
BME VIK, Vajda, 2003
Classical simple cryptosystems
1. Shift Cipher
2. Affine Cipher
3. Substitution Cipher
4. Vigenere Cipher
5. Hill Cipher
6. Permutation Cipher
7.
Stream Cipher (with LFSR)
1. Shift Cipher
P
=
C
=
K
=
Z
26
|K|
=26
E
k
(x)=x+k mod 26
D
k
(y)=y-k mod 26
Character conversion (preprocessing):
A B C ... W X Y Z
0 1 2
22 23 24 25
Example encryption:
x=wewillmeet, k=11
y=HPHTWWXPPE
5

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin