Transcript Introduction to Cryptography

Introduction to Codes,
Ciphers, and Cryptography
Michael A. Karls
Ball State University
1
Introduction


Throughout history, people have had
the need to send messages to other
people in secret!
Methods have been developed to
disguise and break secret messages.
2
Definitions and Terminology


A code is a form of secret communication in
which a word or phrase is replaced with a
word, number, or symbol.
For example, here is a simple code for an
army.



“Attack at dawn” Jupiter.
“The coast is clear”  Tippy-toe.
Each commander and soldier would have a copy
of the codes in some sort of codebook.
3
Definitions and Terminology
(cont.)
A cipher is a form of secret communication in which letters are
replaced with a letter, number, or symbol.
One example of a cipher, attributed to Julius Caesar (1st
Century B.C.), is outlined in the table below.
Basically, the cipher alphabet is the plain alphabet shifted n
spaces left.

For example, if we take n = 14, we get:



“attack at dawn”
“OHHOQY OH ROKB”
Plaintext:
Ciphertext:


Send ciphertext as OHH OQY OHR OKB.
Recipient would need to know how message was created.


Plaintext
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
Ciphertext
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
C
D
E
F
G
H
I
K
M N
B
J
L
z
4
Definitions and Terminology
(cont.)






Cryptography is the science of concealing the
meaning of a message.
It is also used to mean the science of anything
connected with ciphers—an alternative to
cryptology, which is the science of secret writing.
To encrypt a message, one conceals the meaning
of the message via a code or cipher.
Similar definitions hold for encode and encipher.
To decrypt a message, one turns an ecrypted
message back into the original message.
Similar definitions hold for decode and decipher.
5
Notes on Ciphers


For any cipher there is an algorithm,
which is a general encrypting method,
and a key which specifies the exact
details of the algorithm.
For the Caesar cipher,



Algorithm—shift the alphabet.
Key—how many places to shift!
Thus, there are 26 keys for this cipher.
6
Notes on Ciphers (cont.)

The key must remain secure!



If the key is found, the code will be
broken.
If the algorithm is known, the code can
still be secure!
For a code or cipher, the greater the
number of keys, the greater the security!
7
Notes on Ciphers (cont.)


The Caesar cipher is an example of a
substitution cipher.
This cipher is symmetric because
sender and receiver must both know
(have) the key.
8
Ciphers via Modular Arithmetic



Using modular arithmetic, we can make
ciphers!
For any non-negative integers a and n, we
define a mod n to be the remainder when a
is divided by n.
For example,
18 mod 5 = 3, since 18 = 3 x 5 + 3
4 mod 7 = 4, since 4 = 0 x 7 + 4
28 mod 26 = 2, since 28 = 1 x 26 + 2
26 mod 13 = 0, since 26 = 2 x 13 + 0
9
Ciphers via Modular Arithmetic
(cont.)


We can add and multiply numbers mod n too!
For example, here is how to find (27+15) mod 26
and (27 x 15) mod 26.


27+15 = 42 and 42 mod 26 = 16,
so (27+15) mod 26 = 16
or
27 mod 26 = 1 and 15 mod 26 = 15,
so (27+15) mod 26 = (1+15) mod 26 = 16 mod 26 = 16
27 x 15 = 405 and 405 mod 26 = 15,
so (27 x 15) mod 26 = 15
or
(27 x 15) mod 26 = (1 x 15) mod 26 = 15 mod 26 = 15
10
Ciphers via Modular Arithmetic
(cont.)

To find (a+b) mod n:
Add a to b, then find the resulting sum
mod n,
 Or find a mod n, find b mod n, and add the
results mod n.
 Multiplication works in a similar fashion!


Now we are ready to make an additive
cipher!
11
Ciphers via Modular Arithmetic
(cont.)





First, assign 1, 2, …, 26 mod 26 to a, b, …, z.
Next, choose a fixed integer m between 0 and 25.
To get the ciphertext y from plaintext x, add m mod 26, i.e., y = (x+m)
mod 26.
As an example, here is additive cipher alphabet for m=14.
Plaintext
a
b
c
d
e
f
g
h
i
j
k
l
m
Plaintext #
1
2
3
4
5
6
7
8
9
10
11
12
13
Ciphertext #
15
16
17
18
19
20
21
22
23
24
25
0
1
Ciphertext
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
Plaintext
n
o
p
q
r
s
t
u
v
w
x
y
z
Plaintext #
14
15
16
17
18
19
20
21
22
23
24
25
0
Ciphertext #
2
3
4
5
6
7
8
9
10
11
12
13
14
Ciphertext
B
C
D
E
F
G
H
I
J
K
L
M
N
Notice that this is just the Caesar cipher we saw before!
12
The RSA Encryption Scheme


In 1977, MIT mathematicians Rivest,
Shamir, and Adleman announced their
invention of a public key cryptography
scheme.
In order to understand this scheme,
commonly known as RSA, we need
some definitions!
13
Definition of Divisor



Let a and b be integers, with b  0.
We say that b divides a or b is a
divisor of a if a = bc for some integer c.
Notation: b|a
Example 1:
3|24 since 24 = 3 x 8.
Divisors of 12 are: -12, -6, -4, -3, -2,
-1, 1, 2, 3, 4, 6, 12
14
Definition of Greatest Common
Divisor (GCD)



Let a and b be integers, not both zero. The
greatest common divisor (GCD) of a and b
is the largest integer that divides both a and
b.
Notation: (a,b)
Example 2:




Divisors of 6: -6, -3, -2, -1, 1, 2, 3, 6
Divisors of 8: -8, -4, -2, -1, 1, 2, 4, 8
Thus, (6,8) = 2
Since the divisors of 7 are -7, -1, 1, 7,
(7,8) = 1.
15
Definition of Relatively Prime


Two integers whose GCD is 1 are said
to be relatively prime.
Example 3:
Since (7,8) = 1, 7 and 8 are relatively
prime.
16
Definition of Prime Number


A positive integer p is said to be prime
if p>1 and the only positive divisors of
p are 1 and p.
Example 4:
2, 3, and 7 are prime.
6, 8, 10, 100 are not prime
(composite).
17
RSA Scheme (with Alice and
Bob!)

Step 1:

Example 5:

Alice chooses two
huge prime numbers p
and q.
Note: Alice keeps p
and q secret!

p = 47 and q = 59.

18
RSA Scheme (with Alice and
Bob!) (cont.)

Step 2:

Example 5 (cont.):

Alice computes
N = p x q.
Then she computes
k = (p-1)(q-1).
Finally, she chooses
an integer e such that
1<e<N and (e,k) =1.

N = 47 x 59 = 2773.
k = 46 x 58 = 2668.
e = 17.
Choice of e is o.k,
since 1<17<2773 and
(17,2668)= 1.





19
RSA Scheme (with Alice and
Bob!) (cont.)

Step 3:

Example 5 (cont.):

Alice computes
d = e-1 mod k.
Alice publishes her
public key: N, e.
Alice keeps secret her
private key: p, q, d, k.

d = 17-1 mod 2668 =
157.
Alice’s public key:
N = 2773; e = 17.
Alice’s private key:
p = 47; q = 59; d =
157; k = 2668.




20
RSA Scheme (with Alice and
Bob!) (cont.)

Step 4:

Example 5 (cont.):

Suppose Bob wants to
send a message to
Alice.
To do so, he looks up
Alice’s public key,
converts the message
into numbers M<N.

Plaintext is HELLO
HELLO  HE LL O_
Assign 00space;
01A; 02B, … ,
26Z (or use ASCII).



Plaintext Plain #
¨
HE
0805
LL
1212
O_
1500
21
RSA Scheme (with Alice and
Bob!) (cont.)

Step 4 (cont.):

Example 5 (cont.):

Next, for each plaintext
number M, Bob computes:

C = Me mod N
(1)
to get ciphertext number C.

080517 mod 2773 =
542.
121217 mod 2773 =
2345.
150017 mod 2773 =
2417.
Encrypted message is
0542 2345 2417.


22
RSA Scheme (with Alice and
Bob!) (cont.)

Step 5:

Example 5 (cont.):

Bob emails Alice the
encrypted message.
To decrypt, Alice uses her
private key and computes:
M = Cd mod N (2)

0542157 mod 2773 =
805.
2345157 mod 2773 =
1212.
2417157 mod 2773 =
1500.
Decrypted message is
HE LL O_.




23
References

The Code Book by Simon Singh
24