# RSA
> Author:堇姬
# 代號
| 符號 | 意思 |
| --- | ----|
|m|明文 |
|c|密文|
|e|公鑰|
|d|私鑰|
|n|模數|
|p & q|n分解的因數|
|$ϕ(n)$|(p-1)x(q-1)|
# 加密
1. 找到兩個質數$p$ , $q$使得$n=p*q$，需要滿足:
$n>m$ 且 $2q>p>q$
2. 找到一個公鑰e，滿足$gcd(e,ϕ(n))=1$
3. $c=m^e \pmod n$
加密python
```python=
from Crypto.Util.number import *
import gmpy2
import codecs
msg = ""
hex_msg = int(codecs.encode(msg.encode(), 'hex'), 16)
p=getPrime(100)
q=getPrime(100)
n=p*q
e=65537
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
print("phi=",phi)
print("d=",d)
c=pow(hex_msg,e,n)
print("p=",p)
print("q=",q)
print("n=",n)
print("e=",e)
print("c=",c)
```
# 解密
1. 分解$n$，得到$p$ , $q$
2. $ϕ(n)=(p-1)× (q-1)$
3. 找出d，$ed \equiv 1 \pmod {ϕ(n)}$
4. $m=c^d \pmod n$
### 解密script
```python=
from Crypto.Util.number import *
import gmpy2
p=
q=
e = 65537
c =
n=p*q
phi = (q - 1) * (p - 1)
d = gmpy2.invert(e , phi)
print(long_to_bytes(pow(c , d , n)))
```
# 證明解密
>證明 $m=c^d \pmod n$
目前已知$c=m^e \pmod n$
$m \equiv c^d \pmod n \equiv m^{ed} \pmod n \equiv m^{ϕ(n)×k+1} \pmod n$
(因為$ed \equiv 1 \pmod {ϕ(n)}$ 故 $ed=ϕ(n)×k+1$)
故現在只要證明$m \equiv m^{ϕ(n)×k+1} \pmod n$
>證明$m \equiv m^{ϕ(n)×k+1} \pmod n$
分兩種情況討論$m$ , $n$是否互質?
>$m$ , $n$互質
歐拉定理可知
$m^{ϕ(n)} \equiv 1 \pmod {n}$
$m^{kϕ(n)} \equiv 1^k \pmod {n}$
$m^{kϕ(n)+1} \equiv m \pmod {n}$
得證
>$m$ , $n$不互質
因為$m<n$，故$m$只能是$p$的倍數，或是$q$的倍數。(如果m是pq倍數則 $m<n$ 不成立)
假設$m$為$p$之倍數，$m=wp$ , $w \in \mathbb{N}$ ，且$gcd(m,q)=1$
費馬小定理可知
$m^{ϕ(q)} \equiv 1 \pmod {q}$
$m^{k×ϕ(q)} \equiv 1^k \pmod {q}$
$m^{k×ϕ(q)×ϕ(p)} \equiv 1^{k×ϕ(p)} \pmod {q}$
$m^{k×ϕ(n)} \equiv 1 \pmod {q}$
$m^{k×ϕ(n)} \equiv 1+rq \pmod {q}$，$r\in \mathbb{Z}$
兩邊同乘$m$
$m^{k×ϕ(n)+1} = m+rqm$
$m=wp$代入
$m^{k×ϕ(n)+1}=m+rqwp$
$m^{k×ϕ(n)+1}=m+rwn$
存在$\pmod n$時，$m^{ϕ(n)×k+1} \equiv m \pmod n$，得證
>故m,n不管有無互直皆成立，故$m=c^d \pmod n$正確
# 一些常見RSA題目
## n分解
[factordb](http://www.factordb.com/)
## e過小，n過大
$c=m^e \pmod n$
若$m^e <n$
則是否$\pmod n$沒差
$c=m^e$
將c開e次方根即可得到m
```py
from gmpy2 import *
from Crypto.Util.number import *
n=
e= 5
c=
flag = iroot(c, e)[0]
flag_bytes = long_to_bytes(flag)
print(flag_bytes)
```
## p、q相近(p、q為相鄰質數)
$\sqrt{(p×q)}$一定介於p、q間，故我可以用`gmpy2.next_prime()`
```python=
from Crypto.Util.number import *
import gmpy2
p = getPrime(512)
q = gmpy2.next_prime(p)
n=p*q
print(p)
print(q)
print(n)
temp=gmpy2.iroot(n,2)[0]
p=gmpy2.next_prime(temp)
q=n//p
print(p)
print(q)
```
## Common-Factor
如果$n_1,n_2$有一公因數$p$
$n_1=p \times q_1$
$n_2=p \times q_2$
那直接$gcd(n_1,n_2)$就可以找出$p$
```python=
from math import gcd
from Crypto.Util.number import *
n1 =
n2 =
c =
n = n1
p = gcd(n1, n2)
q = n // p
e = 65537
d = inverse(e, (p - 1) * (q - 1))
m = pow(c, d, n)
print(long_to_bytes(m))
```
## Common-Modulus attack
### 條件
$C_1 \equiv M^{e_1} \pmod N$
$C_2 \equiv M^{e_2} \pmod N$
### 證明
$gcd(e_1,e_2)=1$
貝祖等式可知$e_1 \times t+e_2 \times u=1$
所以如果我把
$C_1^{t} \times C_2^{u} \pmod n$可以求出$m$
因為$C_1^{t} \times C_2^{u} \pmod n=M^{e_1t}\times M^{e_2u}\pmod n =m^1\pmod n$
所以可以直接藉由算出$t,u$來求$m$
### code
```python=
from gmpy2 import gcdext
from Crypto.Util.number import *
n =
c1 =
c2 =
e1 =
e2 =
_, t, u = gcdext(e1, e2)
m = pow(c1, t, n) * pow(c2, u, n) % n
print(long_to_bytes(m))
```
## Wiener attack
https://zhuanlan.zhihu.com/p/400818185
```python=
#!/usr/bin/env python3
import gmpy2
from Crypto.Util.number import *
n =
e =
c =
def cf_expansion(n, d):
q, r = n // d, n % d
e = [q]
while r != 0:
n, d = d, r
q, r = n // d, n % d
e.append(q)
return e
def convergents(e):
n, d = [], []
for i in range(len(e)):
if i == 0:
ni, di = e[i], 1
elif i == 1:
ni, di = e[i] * e[i-1] + 1, e[i]
else:
ni, di = e[i] * n[i-1] + n[i-2], e[i] * d[i-1] + d[i-2]
n.append(ni)
d.append(di)
yield (ni, di)
def solve(a, b, c):
k = b * b - 4 * a * c
if k < 0:
return []
sk, complete = gmpy2.iroot(k, 2)
if not complete:
return []
return [int((-b + sk) // (2 * a)), int((-b - sk) // (2 * a))]
def wiener(n, e):
kd = convergents(cf_expansion(e, n))
for i, (k, d) in enumerate(kd):
if k == 0:
continue
phi = (e * d - 1) // k
roots = solve(1, phi - n - 1, n)
if len(roots) == 2:
p, q = roots
if p * q == n:
return (p, q)
p, q = wiener(n, e)
d = inverse(e, (p - 1) * (q - 1))
m = pow(c, d, n)
print(long_to_bytes(m))
```
## Broadcast attack
已知
$C_0=m^e \pmod {N_0}$
$C_1=m^e \pmod {N_1}$
$C_2=m^e \pmod {N_2}$
可以用中國剩餘定理直接求出$M$
$N=N_0 \times N_1 \times N_2$
$K_i= \frac{N}{N_i}$
$m \equiv (C_0K_0K_0^{-1}+C_1K_1K_1^{-1}+C_2K_2K_2^{-1}) \pmod N$
```python=
import gmpy2
import functools
from Crypto.Util.number import *
n0 =
c0 =
n1 =
c1 =
n2 =
c2 =
def crt(a, m):
'''
Input: [a_1, ... a_n], [m_1, ..., m_n]
x = a_1 (mod m_1)
x = a_2 (mod m_2)
...
x = a_n (mod m_n)
Output: x
'''
prod, total = functools.reduce(lambda x, y: x * y, m), 0
for ai, mi in zip(a, m):
Mi = prod // mi
total += ai * Mi * (gmpy2.gcdext(Mi, mi)[1] % mi)
return total % prod
c = crt([c0, c1, c2], [n0, n1, n2])
m, _ = gmpy2.iroot(c, 3)
print(long_to_bytes(m))
```
## LSB Oracle Attack
### 使用場景
有$n,c,e$，給你decrypt，你可以自由決定$c$，但你只會之到最低位(LSB)
```python=
c = int(input())
m = pow(c, d, n)
print(f'm & 1 = {m & 1}')
```
### 原理
已知$m^e \equiv c \pmod n$
先構造
$c \times 2^e$
然後傳入Decrypt可以得到$2m$的LSB
可知
$c \times 2^e \equiv m^e \times 2^e \equiv (2m)^e \pmod n$
> 如果LSB=0，代表 $0< m < \frac{n}{2}$
因為$0< m < \frac{n}{2}$
所以可以知道$2m<n$
$2m \pmod n 取LSB=0$ 因為$2m \pmod n$是偶數
> 如果LSB=1，代表 $\frac{n}{2} < m < n$
因為$\frac{n}{2} < m < n$
所以可以知道$n< 2m < 2n$
$2m \pmod n \equiv 2m-n \pmod n$
$2m-n \pmod n$是奇數(因為$n$是奇數)
所以可得$LSB=1$
這樣就可以利用這種特性來逼近$m$(像是二分搜)
進一步推廣:
構造
$c \times 2^{ke}$
丟入decrypt可以知道，$m \times 2^k$的LSB
因為 $c \times 2^{ke} \equiv 2^{ke} \times m^e \equiv (m \times 2^k)^e \pmod n$
> $\frac{tn}{2^k}<m<\frac{(t+1)n}{2^k}$ 若$LSB=0$， $t$是偶數
$tn<m\times 2^k<(t+1)n$
$2^k \times m \pmod n$的LSB=0
因為
$(2^k \times m)-tn \pmod n$
$tn$是偶數
> $\frac{tn}{2^k}<m<\frac{(t+1)n}{2^k}$ 若$LSB=0$， $t$是奇數
$tn<m\times 2^k<(t+1)n$
$2^k \times m \pmod n$的LSB=1
因為
$(2^k \times m)-tn \pmod n$
$tn$是奇數
## coppersmith
### Known-High-Bits-of-p
```sage=
from Crypto.Util.number import *
p = 0xf57c2c41811e6ef2ca843ffb3359977492f008736e5a3bf6c68e0337b5b93068a74ae01ece215c3c600000000000000000000000000000000000000000000000
n = 113954847378441551522493500984968465847633018880980771590278625504187861167681900872012944653475160211701661736300260194529508005923878166463824278227650138659888808556964271203295384802830741010509561888483441625833400734813257304376142148262455145898253949196509180159943843746225418174830196930437005987137
c = 110960995509593753586414445058090056192022711249034261327970072972237842358984979109482036607371525366794507213368401938143980296502371403082253168041199129918895635161476566764483118093417793289228317962233576518323809551513969693053116919429488737916057885903771772385273439771270145440651596683373514111754
P.<x> = PolynomialRing(Zmod(n))
f = p + x
roots = f.small_roots(beta = 0.5)
if roots:
p = int(p + roots[0])
q = n // p
e = 65537
d = inverse(e, (p - 1) * (q - 1))
m = pow(c, d, n)
print(long_to_bytes(m))
```
## 資源
https://thescipub.com/pdf/jcssp.2006.665.671.pdf
## Pollard's p-1 Algorithm
### B-powersmooth
對於質數$p$，$(p-1)$的質因數$d^k$為$B$，此質數稱為$B-powersmooth$
ex:$1303, 1302=2 \times 3 \times 7 \times 31$那麼質數$1303$就是$31-powersmooth$
### 條件
$(p-1)$的$B$很小，$(p-1)$可以整除$1 \times 2 \times ...\times B$
### 證明
知道$p|n$
建立一個$d=a^{p-1}-1$，可以得到$p|d$
$a^{p-1} \equiv 1 \pmod p$
$d \equiv a^{p-1}-1 \equiv 0 \pmod p$
如果能找到正確的$d$，就可以$gcd(a^{p-1}-1 ,n)=p$
通常$a$從2開始
我們知道$(p-1)|B!$
$2^{B!}=2^{k(p-1)}=1 \pmod p(gcd(2^k,p)=1)$
$gcd(2^{B!}-1,n)=p$
### 流程舉例
```
Input : 1403
Output : Prime factors of 1403 are 61 23.
Explanation : n = 1403, a = 2, i = 2
1st Iteration:
a = (2^2) mod 1403 = 4
d = GCD(3, 1403) = 1
i = 2 + 1 = 3
2nd Iteration:
a = (4^3) mod 1403 = 64
d = GCD(63, 1403) = 1
i = 3 + 1 = 4
3rd Iteration:
a = (64^4) mod 1403 = 142
d = GCD(141, 1403) = 1
i = 4 + 1 = 5
4th Iteration:
a = (142^5) mod 1403 = 794
d = GCD(793, 1403) = 61
Since 1 < d < n, one factor is 61.
d' = 1403 / 61 = 23.
```
### code
```python=
from math import *
def pollard_algorithm(n: int):
a = 2
b = 2
while True:
a = int(a**b%n)
p = int(gcd(a - 1, n))
if 1 < p < n:
return p, n // p
b += 1
```
### 特殊題目-1
給你decrypt但不給你直接decrypt密文
```python=
from Crypto.Util.number import bytes_to_long ,long_to_bytes
e=65537
enc_password=2575135950983117315234568522857995277662113128076071837763492069763989760018604733813265929772245292223046288098298720343542517375538185662305577375746934
n=11015196904712844451510388041761752905176927086891990452575094958019132303573528523602736380438085957767669618870291908056743033313505287486867034650555942
print(pow(2,e,n)*enc_password)
# (2^e*enc_password)^d %n =password
password=int("6468c4c6c4",16)
password=password//2
print(long_to_bytes(password))
```
Sign in with Wallet
Connect another wallet