22-11-04-RSA
JUST conclude the attacks about RSA.
Make a record for myself.
RSA
Algorithm
- produce large primes $p$ and $q$
- calculate $n = p \times q$
- use Euler’s totient function to get $\varphi(n) = (p-1) \times (q-1)$, in code we usually use $N$ or $phi$
- define $e$ which satisfies the condition that $gcd(e, \varphi(n)) = 1$, and the $e$ is between 1 and $\varphi(n)$
- calculate $d$ and the $d$ comes from $de \equiv 1 \mod \varphi(n)$
- encrypt: $c \equiv m^{e} \mod n$
- decrypt: $m \equiv c^{d} \mod n$
- PUBLICKEY: PU{e, n}
- PRIVATEKEY: PR{p, q, d}
Proof
$$
m \equiv c^{d} \mod n \equiv m^{de} \mod n \equiv m^{k\varphi(n) + 1} \mod n \equiv m \mod n
$$
use the Fermat’s little theorem deduce:
$$
m^{n} \equiv m \mod n\
$$
$$
m^{n-1} \equiv m^{\varphi(n)} \equiv 1 \mod n\
$$
$m$, $n$ are relatively-prime
the $m^{k\varphi(n)}$:
$$
m^{k\varphi(n)} \equiv 1\mod n\
$$
$$
\Longrightarrow m^{k\varphi(n) + 1} \equiv m \mod n
$$
$m$,$n$ not relatively-prime
preparation:
$$
gcd(m, n) \neq 1\
$$
$$
n = p \times q\
$$
$$
\Longrightarrow n = kp\
$$
$$
k, p \ are \ relatively-prime
$$
also Fermat’s little theorem:
$$
(kp)^{q-1} \equiv 1 \mod q
$$
based on the properties of con-gruences multiplication property:
$$
(kp)^{(p-1)\times (q-1) \times k} (kp) \equiv (kp) \mod q
$$
substitute the $\varphi(n)$ and $de \equiv 1 \mod \varphi(n)$:
$$
\varphi(n) = (p-1) \times (q-1)\
$$
$$
de = 1 + k \times \varphi(n)\
$$
$$
\Longrightarrow (kp)^{de} \equiv (kp) \mod q\
$$
$$
\Longrightarrow (kp)^{de}=kp + tq
$$
thus, $tq | kq$ and $t|p$ for $q$ is prime:
$$
assume: t = t\times p\
$$
$$
(kp)^{de} = tq + kp = t\times p\times q + k \times p = tn + kp\
$$
$$
(kp)^{de} = m + tn \equiv m \mod n
$$
proved.
Preparation
- gmpy2
- python3.7+
- pycharm
- sagemath
NC CHALLENGE
Before nc real connection, you need to receive the challenge and make a solution about it.
1 | # 1 |
change sha256/tail and crack xxxx
Or use the connecting function:
1 | # 3 |
MODULUS FACTORIZATION
Or we can call it Original_RSA.
The main target in RSA problems is to factorize n to p and q.
Here is the code of Original_RSA which is the basic attack among RSA attacks.
1 | def Original_RSA(p, q, e, c, n): |
BUT HOW TO FACTORIZE THE $n$?
It is the significant question. Follows are some solutions that I met.
Factorize
factordb
A database contains many $n$ that has been factorized.
yafu-x64
The $p$,$q$ differ very well or a little or $p$,$q$ are smooth and produced by $\rho -1 $or $\rho + 1 $.
usage
yafu-x64 factor()
yafu-x64 factor(@) -batchfile [filename] !remember the number saved in file and need a
\n
msieve153
Which is similar to yafu-x64
RSAConverter
Based on CRT.
usage
$n$, $d$ convert to hex and delete
0x$e$ convert to hex and delete
x
fermath factorization
p,q have a little difference
- p or q created by
next_prime()- find the Reference Substance
n_2which can be produced byiroot(n, 2)[0] - p and q are primes, and $p<n_2<q$
- we can get $q$ by
next_prime(n_2) - and
p = n // q
- find the Reference Substance
- p and q are similar but not neighbors
- also find the
n_2 - with
n_2as a center, step size 1 and right - if find $p$ and $q$ satisfied the condition, and we get the true $p$ and $q$
- also find the
1 | # Fermat Factorization 2 |
backdoor
$$
Prime = k \times M + 65537^{a} \mod M
$$
1 | def RSA_Backdoor(n): |
xor factorization
usage
xor_factor.py n x
pollard’s p-1
This part only give the solution.
Detailed introduction needs time to be written.
$$
(p-1) | B!\
$$
$$
2^{B!}\equiv 1 \mod p
$$
1 | from primefac import pollard_pm1 |
williams’s p+1
As above.
1 | from primefac import williams_pp1 |
known phi
1 | from math import gcd |
sage
$n = a^2 + b^2$
1 | two_squares(n) |
$n = a^2 + b^2 + c^2$
1 | three_squares(n) |
Quadratic Sieve
1 | qsieve() |
find prime factors
- elliptic curve factorize
1 | ecm() |
- just prime factorize
1 | prime_divisors() |
Others
- lenstra elliptic curve factorization
- birthday attack
- ……
SAME MOD
The attack is based on the Homomorphic Encryption and Extended Euclidean Algorithm.
Usually, we have two pairs of $c$ and $e$ and both them have the same modulo.
*REMEMBER that the encrypted m should be same. *
$$
c_{1} \equiv m^{e_{1}} \mod n\
$$
$$
c_{2} \equiv m^{e_{2}} \mod n
$$
Use Extended Euclidean Algorithm, the eqution follows:
$$
r \times e_{1} + s \times e_{2} = gcd(e1, e2)
$$
Based on the Multiplicative homomorphism, and we can make a conversion.
$$
c_{1}^{s} \times c_{2}^{r} \equiv m^{r\times e_{1} + s\times e_{2}} \mod n
$$
$e_{1}$, $e_{2}$ are primes
If $e_{1}$ and $e_{2}$ are primes, $gcd(e_{1}, e_{2}) = 1$, and we can substitute the integer into the equation above.
$$
c_{1}^{s} \times c_{2}^{r} \equiv m \mod n
$$
$e_{1}$, $e_{2}$ not primes
- $gcd(e1, e2)$ and $\varphi(n)$ are not relatively-prime.
May use Rabin Algorithm to solve this problem. For another word, the problem converts to the Low_Exponent_e2 problem.
- $gcd(e1, e2)$ and $\varphi(n)$ are relatively-prime.
Thus, just use iroot(m, g) and we get the true $m$. REMEMBER that before the calculation we ought to % n first.
1 | def Same_Mod_RSA(e1, e2, c1, c2, n): |
The code ignores that gcd($e_{1}$, $e_{2}$) and $\varphi(n)$ are not relatively-prime.
Multiplicative congruence
We use multiplicative congruence to simplify our calculation.
It usually gives us one same modulo $n$ and two more pairs of $c$, $e$.
FOR EXAMPLE:
1 | N = |
The deduction is as follows:
$$
g_{1} \equiv e_{1} \cdot r_{1} + e_{2} \cdot s_{1} \
$$
$$
g_{2} \equiv g_{1} \cdot r_{2} + e_{3} \cdot s_{2}
$$
The three public keys satisfy $gcd(e_{1}, e_{2}, e_{3}) = 1$, so $g_{2} = 1$.
We can get the equation that $1\equiv (e_{1}\cdot r_{1} + e_{2} \cdot s_{1})\cdot r_{2} + e_{3} \cdot s_{2}$.
Expand it:
$$
1 \equiv (r_2\cdot r_1)\cdot e_1 + (s_1 \cdot r_2)\cdot e_2 + s_2\cdot e_3
$$
$$
c_1 \equiv m^{e_1} \mod n
$$
$$
c_2 \equiv m^{e_2} \mod n \
$$
$$
c_3 \equiv m^{e_3} \mod n \
$$
$$
\Longrightarrow c_1^{r_2\cdot r_1}\cdot c_2^{s_1\cdot r_2} \cdot c_3^{s_2} \equiv m \mod n
$$
1 | …… |
MODULO RELATED
$n_{1}$ and $n_{2}$ are relatively-primes
When they encrypt the same message $m$，it exists THE MODULO RELATED ATTACK.
Deduction
$$
n_1 = p \times q_1
$$
$$
n_2 = p \times q_2\
$$
Ignore the possibility that $1 \times n_1$ and $1 \times n_2$
$$
p = gcd(n_1, n_2) \
$$
$$
q_1 = n_1 // p
$$
$$
q_2 = n_2 // p
$$
$ p$ can be calculated with function gcd() , and use division to solve out the $q_1$ and $q_2$.
The problem converts to the Original_RSA.
Solution
1 | def RSA_NPM(n1,n2,e,c1): |
Remember that $n_1$ and $c_1$ are one-to-one!
LOW EXPONENT
e = 3
or one-to-one function
JUST Bruck.
- $m^e < n$, means that $k = 0$ in code below
- $m^e > n$
1 | def RSA_Low_Exponent_e3(c,e,n): |
$e$ and $\varphi(n)$ are not relatively-prime
e = 2
Rabin
PART1 $m_p$ and $m_q$
Split into two scenarios for discussion:
- $p$ and $q$ are satisfied $p \equiv q \equiv 3 \mod 4$.
$$
m_p \equiv c^{\frac{1}{4}(p + 1)} \mod p
$$
$$
m_q \equiv c^{\frac{1}{4}(q + 1)} \mod q
$$
- $p$ and $q$ are different to 1.
$$
m_p \equiv c^{\frac{1}{2}} \mod p
$$
$$
m_q \equiv c^{\frac{1}{2}} \mod q
$$
PART2 Calculated $y_p$ and $y_q$ with Extended Euclidean Algorithm whose function is gmpy2.gcdext().
$$
y_p \cdot p + y_q \cdot q = 1
$$
PART3 Solve out four plaintexts.
$$
a \equiv (y_p \cdot p \cdot m_q + y_q \cdot q \cdot m_p) \mod n
$$
$$
b \equiv n - a
$$
$$
c \equiv (y_p \cdot p \cdot m_q - y_q \cdot q \cdot m_p) \mod n
$$
$$
d \equiv n - c
$$
Thus, we will get four different plaintext, and one of them is the true plaintext.
Here is the complete code:
1 | def RSA_Rabin_e2(c,n,p,q): |
e != 2
If $e$ is not equal to 2, we use another way to calculate the final $m$.
For example, $gcd(e, \varphi(n)) = a$. We can divide $e$ to get the equation $gcd(e//a, \varphi(n)) = 1$ to solve the private key $d$.
Finally, we get the $m^{a}$. We use iroot($m^{a}$, a)[0] to get the final plaintext $m$.
1 | # We define phi as N |
AMM
The same $e$ is too large to solve out.
1 | import random |
RSA_LEAKAGE
Leakage_d
Use RSAConverter.
- $n$, $d$, hex(), delete
0x - $e$, hex(), delete
x
Leakage_dp&dq
Dedection and keypoint!
Prepare and make a definition to $d_p$ and $d_q$.
$$
d_p \equiv d \mod p-1
$$
$$
d_q \equiv d \mod q-1
$$
After deductions, we can get four significant equations or relations.
$$
q \times InvQ \equiv 1 \mod p
$$
$$
m_p \equiv c^{d_p} \mod p
$$
$$
m_q \equiv c^{d_q} \mod q
$$
$$
m \equiv (((m_p - m_q)\times InvQ)\mod p)\times q + m_q
$$
And make the equations convert to codes. Here is the main function:
1 | def RSA_Leakage_dp_dq(dp, dq, p, q, c): |
Leakage_dp
basic
Known:
$$
d_p \equiv d \mod (p-1)
$$
$$
d\times e \equiv 1\mod N \equiv 1 \mod (p-1)(q-1) \tag{1}
$$
Make full use of the two known equations and deduce the key condition to obtain the final $p$ and $q$.
$$
d_p \times e \equiv d \times e \mod (p-1) \equiv de + k_1(p-1) \tag{2}
$$
Substitute (2) to (1):
$$
k_1(p-1) + d_p e = 1 + k_2(p-1)(q-1)
$$
$$
d_pe - 1 = (p-1)[k_2(q-1) -k_1]
$$
Assume $k_2(q-1) - k_1$ is $x$, and $x$ is range from 0 and $e$, and we can figure out the $p$ from the equation:
$$
p = \frac{d_{p} e-1}{x} + 1
$$
If we brute the $p$ in range(0, e) and $q = n \div p$ is prime or Integer, we will get the true $p$ and $q$. The code is as follows:
1 | def RSA_Leakage_dp(n,e,dp,c): |
dp_extension-1 $n = p^{b} \cdot q$
reference: Larrozo
relate: [2020YCB]Power
1 | def dp_hensel(c, e, dp, p, b): |
dp_extension-2 coppersmith known dp high
Given: $n, e, dp_0,c,k$
the $dp_0$ is the high-digits$(nbits - k)$ of dp, meaning that $dp_0 = dp >> k$
Solve: use the coppersmith-high p
dp_extension-3 $p = gcd(m^{e\cdot dp} - m, n)$
LARGE $e$
Wiener Attack
$d < N^{0.25}$
original deduction
From the RSA proof, we have a DEFAULT RULE:
$$
e\times d \equiv 1 \mod \varphi(n)
$$
If satisfied conditions, we will get the deduced equation:
$$
e \times d = k \times \varphi(n) + 1 \approx k \times \varphi(n)
$$
In cryptography, the $n$ is usually very large. So, we can make a connection with $\varphi(n)$:
$$
\varphi(n) \approx n
$$
Thus, we can get the final deduction:
$$
e\times d \approx k \times n
$$
$$
\frac{e}{n} \approx \frac{k}{d}
$$
continued fraction
Use Extended Euclidean Algorithm, and we will get the equation. Here is the proof-picture:
For the example, we can get the continued fraction that 34/99 -> [0, 2, 1, 10, 3].
1 | def continued_fra(x,y): |
gradual fraction
1 | def gradual_fra(cf): |
Veda’s theorem
1 | def solve_pq(a,b,c): |
main Wiener
1 | def RSA_Wiener_Attack(e,n): |
Boneh-Durfee Attack
$d< N^{0.29}$
COPPPERSMITH
high m
1 | # high m |
high p
1 | # high p |
low d
1 | # low d |
crt/broadcast
1 | # crt/broadcast |
Franklin–Reiter related-message attack
1 | n = |
Boneh Burfee Attack
1 | # Boneh Burfee Attack |
Addiction
When we obtain the $m$, there are different ways to get flag.
- long_to_bytes()
Long integer converts to bytes.
- ASCII
The beginning of $m$ is 1, and it may convert to some invisible characters.
TBC