Posts Tagged - algorithm

RSA Small Key Problem

Given public key = (7, 33).

Find private key (d).

n = 33 (modulus)

e = 7 (exponent)

let’s factoring n

n = p * q

33 = ? * ?

floor(sqrt(n)) = floor(sqrt(33)) = 5

33 mod 5 = 3 « not 0

33 mod 4 = 1 « no need to test (except for 2 all other prime numbers are odd)

33 mod 3 = 0 « we got p = 3

p = 3

33 = 3 * ?

Read More

RSA Algorithm

Key Generation

  1. Generate two random primes, p and q, e.g p=3, q=11.

  2. Compute n = pq, n = 3 * 11 = 33.

  3. Compute phi = (p-1)(q-1) = (3-1)(11-1) = 20

  4. Choose an integer e, 1 < e < phi, such that gcd(e, phi) = 1, e.g e = 7, gcd(7, 20) = 1

  5. Compute the secret exponent d, 1 < d < phi, such that (e * d) mod phi = 1, (7 * d) mod 20 = 1, d = 3

Read More

Square and Multiply

11^37 = ?

37 = 100101 in binary

  • 1 -> first “One” lists number = 11

  • 0 -> square = (11)^2

  • 0 -> square = ((11)^2)^2

  • 1 -> square + multiply = (((11)^2)^2)^2*11

  • 0 -> square = ((((11)^2)^2)^2*11)^2

  • 1 -> square + multiply = (((((11)^2)^2)^2*11)^2)^2*11

Read More