Random Walk

Public Key Encryption Math Problems

Public Key Encryption Math Problems

In order to have better understanding of public encryption methods, I spend some time understanding math problems behind them. Most of these problems provides a Trapdoor functionality.

Trapdoor

Trapdoor is a function that is easy to do it in one way and really hard to do it the otherway. in other words having A we can easily compute B. But by having B is really hard to get back to A. This hardness can be due to the cost or time needed.

A --> B
A

the integer factorization problem

If we have two number $A$ and $B$ and $ C = A * B $, break C back to A and B is called integer factorization. Prime factorization is a subset of the problem with an extra constraint that factors should be prime. e.g. $$ 864 = 2 * 2 * 2 * 2 * 2 * 3 * 3 * 3 $$

This become interesting and hard problem if :

  • $A$ and $B$ are prime numbers
  • $A$ and $B$ are very large (about two thousand bits long)
  • $A$ and $B$ are randomly chosen

then $C$ is called semiprime.

Some of the methods built on top of this problem are :

  • RSA (Rivest–Shamir–Adleman)
  • Paillier
  • Benaloh
  • Blum–Goldwasser
  • Cayley–Purser
  • Damgård–Jurik
  • GMR
  • Goldwasser–Micali
  • Rabin
  • Okamoto–Uchiyama
  • Schmidt–Samoa

Hardness:

for 1024-bit RSA, it is estimated by having 100 Machines, it will take more than 2000 years to break it.

co-prime: two integers a and b are said to be relatively prime or co-prime if the only positive integer that divides both of them is 1 ( $gcd(a,b) = 1$ )

Euclidean algorithm is an efficient method for computing the gcd of two numbers

Bézout's identity: let a and b be nonzero integers and let d be their gcd. Then there exist integers x and y such that

$$ax+by=gcd(a,b)$$

RSA simple implementation

This code is just for learning, please do not use it for any production code. addopted from here

In [7]:
# pick prime numbers (P, Q) and E such that:
#  1: P and Q are prime; picked at random.
#  2: 1 < E < (P-1)*(Q-1) and E is co-prime with (P-1)*(Q-1)
P=97  # First prime
Q=83  # Second prime
E=53  # usually a constant; 0x10001 is common, prime is best

Brute-force primality test

In [14]:
def isPrime(x):
    if x%2==0 and x>2: return False     # False for all even numbers
    i=3                                 # we don't divide by 1 or 2
    sqrt=x**.5                          
    while i<sqrt:
        if x%i==0: return False
        i+=2
    return True

# tests
# print(isPrime(P))
# print(isPrime(Q))
# print(isPrime(E))
# print(isPrime(1))
# print(isPrime(4))
In [ ]:
'''
Euclidean algorithm to detect the greatest common divisor of a and b
'''
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

RSA settings

In [16]:
# Product of P and Q is our modulus; the part determines as the "key size".
MOD=P*Q

# E is the public exponent 


print(MOD)

8051

the discrete logarithm problem

  • a^b mod (prime number) p = r when prime number the solution is equally likely to be any number between zero and prime number

    reverse is hard (to detect b having a, p, r )

    if we use a large prime number (e.g. hundreds of digits)

     - all human computation power, thousends of years

 [time needed to find it]
e.g.
Cramer–Shoup
DH
DSA
ECDH
ECDSA
EdDSA
EKE
ElGamal
MQV
Schnorr
SPEKE
SRP
STS

the elliptic-curve discrete logarithm problem

- ECC requires smaller key size  (256bits vs 3072bits for RSA)  (recommended : 384)

- draw eleptic curve in python

    max is like mirror (key size)
    private key = "n" (number of times running the method)  ??

    starting point A
    ending point Z


    import numpy as np
    import matplotlib.pyplot as plt

    def main():
        a = -1
        b = 1

        y, x = np.ogrid[-5:5:100j, -5:5:100j]
        plt.contour(x.ravel(), y.ravel(), pow(y, 2) - pow(x, 3) - x * a - b, [0])
        plt.grid()
        plt.show()

    if __name__ == '__main__':
        main()

the elliptic-curve discrete logarithm problem (ECC is here)

p Field that the Curve is defined over
a,b = Values define the Curve
G = the generator point
n = prime order of G
h = cofactor

Post-quantum cryptography

Post-quantum cryptography https://en.wikipedia.org/wiki/Post-quantum_cryptography

PQCrypto conference series since 2006 Shor's algorithm

In [ ]: