Crypto tools
shift-ekey-search.py
Exhaustive key search for Shift Cipher.
vigenere-friedman.py
Ref: https://en.wikipedia.org/wiki/Letter_frequency https://github.com/cbornstein/python-vigenere/blob/master/vigenere.py
OTP-encryption-matrix.py
DES-key.py
AES128-key.py
egcd()
extended euclidean algorithm
Input: a, b (a > b) Output: x, y, where ax + by = gcd(a, b)
solve_congruences_system()
Use Chinese Remainder Theorem to solve a system of congruences:
The system of r congruences
Input: a[], m[], where m[i], m[j] are pair-wise relatively prime
calc_keys()
Calculate keys Input: p, q Choose: e = 65537 Output: N, phi_N, d pubkey: (N, e) prikey: (N, d)
RSA Key generation algorithm (original):
- Generate 2 large random primes, p and q, of approximately equal size such that their product n=pq is of the required bit length
- Compute N=pq and
$\phi(N)$ =(p−1)(q−1) - Choose an integer e,
$1 \lt e \lt \phi(N)$ , such that gcd(e, $\phi(N)$) = 1 - Compute the secret exponent d,
$1 \lt d \lt \phi(N)$ , such that$ed \equiv 1 \mod \phi(N)$ - The public key is (N, e) and the private key is (d, p, q). Private key also can be written as (N, d)
e can be chosen from 3,5,17,257,65537
Encryption
Input: pubkey + plaintext
m - plaintext (int) c - ciphertext (int)
Decryption
Input: prikey + ciphertext
Rainbow table
RSA-decryption-table.py
: generate decryption table (RSA-dec-table.txt
)
RSA-dec-table.txt
: then decryption table
Hastad's Broadcast attack
hastad-broadcast-attack.py
hastadBroadcastAttack()
in RSA.py
for factorization
Idea: construct $n = x^2 - y^2 = (x + y)(x - y) $ for factorization
Find
So
Given
Assign exponent vector to the right-hand side of the congruence:
Multiplying right-hand sides <-> Adding exponent vactors
Perfect square <-> Exponent vector with even components
Recipes of T
-
$z = j + \lceil \sqrt{kn} \rceil (\mod n)$ ,$j = 0,1,...$ , $k = 1,2,...$. Yields$z^2 (\mod n)$ that are small -
$z = \lfloor \sqrt{kn} \rfloor (mod n)$ , $k = 1, 2, ...$. Yields$-z^2(\mod n)$ that are small
Factor-Base B
Factor base is a small set of prime numbers
- v0: simply 2 loops
- v1: find the power set of the set containing all exponent vectors. For each subset, check whether the perfect square can be constructed.
- v2: according to the exponent vectors, set constraints and solve with
z3
solver
elGamal.py
Let
Define the plaintext space as
Set the keyspace as
PubKey:
PriKey: a, the secret exponent
Encryption:
Decryption: take
shanks.py
Find x, such
p should be prime
(x, y) is a point on
point-compress((x, y)) =
point-decompress((x, parity)) =
- parity = 0, y = Even square root (mod p) of f(x)
- parity = 1, y = Odd square root (mod p) of f(x)
Plaintext space
Ciphertext space
Keyspace
Pubkey:
Prikey: m
Encryption:
Decryption:
Given ciphertext pair