ソフトウェアエンジニアの技術ブログ：Software engineer tech blog

Deterministic
– for the same key, a particular plaintext is always mapped to a particular ciphertext
– special-case plaintexts 0, 1, or -1 produce ciphertexts 0, 1, or -1 regardless of keys
Malleable
– Transforming a ciphertext into another leads to predictable transformation to plaintext
For c = m^e mod n, attacker change c to s^exc
-Receiver gets sxm instead of m

RSA in practice
– PKCS(public key cryptography standard) uses OAEP(optimal asymmetric encryption padding)
– Append padding(seeded from random byte) as prefix to m

Diffie and Hellman Key Exchange
– first published public-key algorithm
– by diffie and Hellman in 1976 along with the exposition of public key concepts
– Used in a number of commercial products
– Practical method to exchange a secret key securely that can then be used for subsequent encryption of messages
– Security relies on difficulty of computing discrete logarithms

Given KU = and KR =

encryption: c = m^2 mod n, m < n decryption: m = c^d mod n signature: s = m^d mod n, m < n verification: m = s^e mod n Given pub = and priv =
n = p*q,Θ(n) = (p-1)(q-1)
exd = 1 mod Θ(n)
x^exd = x mod n
encryption: c = m^e mod n
decryption: m = c^d mod n = m^exd mod n = m mod n = m(since m < n) digital signature (similar) 88^7 mod 187 = 11 -> 11^23 mod 187 = 88 -> plaintext 88

Factoring an integer with at least 512-bit is very hard!
But if you can factor big number n then given public key , you can find d, and hence the private key by:
knowing factors p, q, such that, n = p*q
then compute Θ(n)=(p-1)(q-1)
then find d such tat exd = 1 mod Θ(n)

Multiplication modulo M

Multiplicative inverse: multiplication MOD
M yields 1
e.g., M=10, 3 and 7 are inverse of each other because 3*7 MOD 10 = 1

Only some numbers have inverse
but 2, 5, 6, 8 do not have inverse when M=10

Use Euclid’s algorithm to find inverse
Given x, n, it finds y such that x*y mod n = 1
Only the numbers relatively prime to n has MOD n multiplicative inverse

Totient Function
x is relatively prime to n: no common factor other than 1
Totient function Θ(n): number of integers smaller than n and relatively prime to n
if n is prime, Θ(n)= n-1
if n = p*q, and p, q are primes, Θ(n)=(p-1)(q-1)
if n = p*q, and p, q are relative prime to each other, Θ(n)=Θ(p)Θ(q)

X^y mod n = X^ymodΘ(n)mod n
if y = 1 mod Θ(n)then x^y mod n = x mod n

RSA(Rivest, Shamir, Adleman)
– Widely used, and one of the first(1977)
– Support both public key encryption and digital signature
– Assumption/theoretical basis:
Factoring a very large integer is hard

Variable key length
Variable plaintext block size
– Plaintext treated as an integer, and must be “smaller” then the key
– Ciphertext block size is the same as the key length

Modular arithmetic
RSA
Diffie-Hellman

Public key algorithms are based on modular arithmetic
– modular addition
– modular multiplication
– modular exponentation

Addition modulo (MOD) M
Additive inverse: addition MOD M yields 0
e.g. M=10, for k=2, its inverse is k^-1=8 because 2+8 MOD 10 = 0
Reversible: by adding the inverse
– convenient for decryption
e.g., for c = 3, p = c + k = 3+2 MOD 10 = 5;
p+k^-1 = 5+8 MOD 10 = 3 = c

Calculating AB mod C for any B

Find: 5117 mod 19
Step 1: Rewrite B into its binary form

117 = 1110101 = 1 2^6 +1 2^5 + 1 2^4 + 1 2^2 + 1*2^0
117 = 64 + 32 + 16 + 4 + 1

Step 2: Convert to Powers of 2 and find the mod

5117 mod 19 = (52^6 52^5 52^4 52^2 52^0)

51 mod 19 = 5
52 mod 19 = (55) mod 19 = 25 mod 19 = 6
54 mod 19 = (66) mod 19 = 36 mod 19 = 17
58 mod 19 = (1717) mod 19 = 289 mod 19 = 4
516 mod 19 = (44) mod 19 = 16 mod 19 = 16
532 mod 19 = (1616) mod 19 = 256 mod 19 = 9
564 mod 19 = (99) mod 19 = 81 mod 19 = 5

Step3: Combine the individual powers to find the final answer

5117 mod 19 = (564532 5165451 ) mod 19
= (564 mod 19 532 mod 19 516 mod 19 54 mod 19 51 mod 19 )mod 19
= 61200 mod 19
= 1

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)