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

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
Computionally infeasible to find m1=m2 s.t. H(m1)=h(m2)
strong collision resistant

Requirements for a practical application of a hash function
The one way property
Hash functions are unique to each message

Sender: Message with encrypted hash code
-> generate an un-encrypted hash code
-> create an alternate message
-> Receiver: Forged message with encrypted hash code

Hash Function Weaknesses
-> Pigeonhole principle
-> The Birthday Paradox

n = numbers of pigeons
m = number of holes
n = m There is one pigeon per hole
n > m Then at least one hole must have more than one pigeon

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