Month: July 2017

Modular Multiplication
(A B) mod C = (A mod C B mod C) mod C

Example:
A mod 17 = 15
B mod 17 = 9

(AB)mod 17 =
(15 9)mod 17 = 16

(2611 135) mod 13 is equivalent to:

Solution:
(2611 mod 13 135 mod 13)mod 13
(11 * 5)mod 13
(55)mod 13 = 3

Example: 7256 mod 13

71 mod 13 = 7
72 mod 13 = (7 mod 13 7 mod 13)mod 13 = (7 7)mod 13 = (49)mod 13 = 10
74 mod 13 = (10 10)mod 13 = 100 mod 13 = 9
78 mod 13 = (9 9) mod 13 = 81 mod 13 = 3
716 mod 13= (3 3)mod 13 = 9 mod 13 = 9
732 mod 13=(9 9)mod 13 = 81 mod 13 = 3
764 mod 13 = (3 3) mod 13 = 9 mod 13 = 9
7128 mod 13 = (9 9) mod 13 = 81 mod 13 = 3
7256 mod 13 = (3 * 3) mod 13 = 9 mod 13 = 9

Congruence:
A == B mod(C)
means
A mod(C) = B mod(C)

For Example:
(26 mod 5 = 1) and (11 mod 5 = 1) so ….
(26 == 11 mod 5)

-4(mod 3) = 2
find the mod for each answer:
-33(mod 3) = 0
-1(mod 3) = 2
12 (mod 3) = 0
35 (mod 3) = 2
45 (mod 3) = 0

Answer:
x = -1 or x = 35

Given: A mod 3 = 1 and (-20 + A)mod 3 = Y
Solve for Y

Solution:

(-20 + A) mod 3 = (-20 mod 3 + A mod 3)mod3
(-20 + A) mod 3 = (1 + 1)mod 3
(-20 + A) mod 3 = 2 mod 3
(-20 + A) mod 3 = 2

(918 – 236) mod 20 = Y

Solution:
(918 mod 20 + (-236 mod 20)) mod 20

(18 + 4)mod 20 = 2

When dealing with negative numbers recall:
if A is a negative number: A = Q * B + R
Q = floor(A/B)

For example:
-6 mod 18

Q= -1…floor(-6/18)
A QB + R
-6 = -1 18 + R
12 = R
-6 mod 18 = 12

Solution: -27 mod 4
Q = floor(-27/4) = floor(-6.75) = -7
A = Q B + R
-27 = -7 4 + R
1 = R

Solution: -7 mod 6
A = Q * B + R
-7 = floor(-7/6) + R
-7 = -12 + R
5 = R

Solution: -17 mod 7
A = Q B + R
-17 = floor(-17/7)7 + R
-17 = -3*7 + R
4 = R

Mod is the remainder of a division between two integers

For example:
27 mod 7 is equivalent to asking:
27 / 7 = 3 r 6
26 mod 7 = 6

Solution: 34 mod 5
34 / 5 = 6 r 4
34 mod 5 = 4

Solution: 121 mod 3
121 / 3 = 40 r 1
121 mod 3 = 1

Solution: 67 mod 23
67 / 23 = 2 r 21
67 mod 23 = 21

Solution: 45 mod 32
45 / 32 = 1 r 13
45 mod 32 = 13

Solution: 908 mod 534
908 / 534 = 1 r 374
908 mod 534 = 374

– Break a message into blocks
– Apply block cipher on the blocks
– Is that it?

Electronic Code Book(ECB)
(M1==M3) -> (C1==C3)

Lack the basic protection against integrity attacks on the ciphertext at message level(i.e., multiple cipher blocks)
Without additional integrity protection
cipher block substitution and rearrangement attacks
fabrication of specific information

Protecting Message Integrity
Only send last block of CBC(CBC residue) alog with the plaintext
Any modification in plaintext rsult in a CBC residue computed by the receiver to be different from the CBC residue from sender
Ensures integrity

simply sending all CBC blocks(for confidentiality) replicating last CBC block(for integrity) does not work
Should use two separate secret keys: one for encryption and the other for generating residue(two encryption passes)
Or, CBC(message|hash of message)

48 bits => 32 bits(8*6 => 8*4)
2 bits used to select amongst 4 substitutions for the rest of the 4-bit quantity

Security of DES
– key space is too small(2^56 keys)
Exhaustive key search relative easy with today’s computer
– S-box design criteria have been kept secret
– Highly resistant to cryptanalysis techniques published years after DES

Triple DES
(a)Encryption p -> E -> D -> E -> C
(b)Decryption: C -> D -> E -> D -> P
K1=K3 result in an equivalant 112-bit DES which provides a sufficient key space
Distinct K1, K2, K3 results in an even stronger 168-bit DES
Can run as a single DES with K1 = K2

Advanced Encryption Standard
In 1997, the U.S. National Institute for Standards and Technology(NIST) put out a public call for a replacement to DES
It narrowed down the list of submissions o five finalists, and ultimately chose an algorithm(Rijndael) that is now known as the Advanced Encryption Standard
New (Nov. 2001) symmetric-key NIST standard, replacing DES
Processes data in 128 bit blocks
Key length can be 128, 192, or 256 bit

Block cipher primitives
DES
AES
Encrypting large message
Message integrity

Block Cipher Scheme
plaintext block of length n -> Encrypt -> cipher block of length n

Block Cipher Primitives
Confusion:
an encryption operation where the relationship between the key and ciphertext is obscured
achieved with substitution

Diffusion
an encryption operation where the influence of one plaintext bit is spread over many ciphertext bits with the goal of hiding statistical properties of the plaintext
achieved with permutation

Both confusion and diffusion by themselves cannot provide (strong enough) security
Round: combination of substitution and permutation, and o so often enough so that a bit change can affect every output bit

Data Encryption Standard
64 bit M -> DES Encryption -> 64 bit C
56 bits
Published in 1977, standardized in 1979
Key:64 bit quantity=8-bit
parity+56-bit key
Every 8th bit is a parity bit
64 bit input, 64 bit output

Data Encryption Standard
DES Top view
64-bit input
permutation
round1
round2
swap
permutation
64-bit output

Bit permutation(1-to-1)
Input <-> Output

DES Round
32 bits Ln, 32 bit Rn
Can be expressed as: Ln+1 = Rn, Rn+1 = LnXORM(Rn,Kn)

Decryption
-Apply the same operations key sequence in reverse
Round1 of decryption uses key of the last round in encryption
-Each round:
Input: Rn+1|Ln+1
Due to the swap operation at the end of encryption
Output:Rn|Ln
The swap operation at the end will produce the correct result:L|R

Mangler Function
The permutation produces “spread” among the chunks/S-Boxes!

– protects a message without needing to first arrange for sender and receiver to have the same secret key
– Equates to the same thing as a sealed envelope containing an unsigned letter

Message
random symmetric key -> encrypted message -> digital envelop
receiver’s public key -> encrypted symmetric key -> digital envelope

plaintext input -> encryption algorithm -> decryption algorithm(reverse of encryption algorithm)-> plaintext output

y = E[K,X], X=D[K,Y]

Comparison of Encryption Algorithm
DES = Data Encryption Standard
AES = Advanced Encryption Standard

Plaintext block size(bits)
Ciphertext block size(bits)
Key size(bits)

Asymmetric Encryption
– plain text:readable message or data that is fed into the algorithm
– encryption algorithm: perform transformations on the plaintext
– public and private key: pair of keys, one for encryption, one for decryption
– ciphertext: scrambled message produced as output
– Decryption key: produces the original plaintext

Digital Signatures:
plaintext message -> hash function -> hashtag -> encrypted signed message -> compare the hash value sent with hash value generated -> reject message

Generate hash code of unsigned certificate -> Encrypt hash code with CA’s private key to form signature -> signed certificate -> decrypt signature with CA’s public key to recover hash code -> recepient can verify signature by comparison hash code values

Simple Ciphers
– Caesar’s cipher(or, shift cipher):
e.g., A->D, B->E
that is, shift by an offset n:
-(letter + n) mod 26
only 26 possible ways of secret coding
– Monoalphabetic cipher(or, substitution cipher):
generalization, arbitrary mapping of one letter to another
26!, ~4*10^26 or ~ 2^88
Attack with statistical analysis of letter frequencies

Vigenere Cipher

What should be kept secret?
Kerchhoff’s principle
a cryptosystem should be secure even if the attacker knows all details about the system, with exception of the secret key
In practice:
Only use widely known ciphers that have been crypto analyzed for several years by good cryptographers
e.g., established standards

secret key cryptography:
one key same key for encryption and decryption
public key cryptography:
two keys
public for encryption, private for decryption
private for signing and public for verification

Hash Functions
compute message digest of data of any size
fixed length output: 128-512 bits
easy to compute H(m)
Given H(m), no easy way to find m
– one-way function
Given m1, it is computationally infeasible to find m2=m1 s.t. H(m2)= H(m1)
weak collision resistant
Computationally infeasible to find m1 = m2 s.t. H(m1)=H(m2)
strong collision resistant

Hash Functions for passwords
hash function, stored hash of password -> access granted