RSA Notes 3

huangx607087学习RSA的笔记(3)

O-About

一个密码学废物的学习笔记3,很菜,别看。以后会不定时地补充

为了期末考试,30天的CTF学习都摸了,现在风信子里面的大佬越来越多了,我也变得越来越菜。不过还好,自己的高数过了,寒假没事就可以多搞搞CTF了(哦对,还有英语6级,争取大一下半年过掉)

约定:此博客中如果出现除法,未特殊说明的,均为向下取整的整除!

I-RSA中$\gcd(\phi,e)\not = 1$的情况

0x01 题目背景&引例

NCTF中有一道RSA题目给出了$e,\phi$不互素的情况,这就意味着$e,\phi$的逆元$d$不存在,因此我们也就无法使用常规的方法来分解因式。

为了探讨大数字的一般性结论,我们先从小的数字开始,看一个引例:

在数字极小的时候,我们假设$e=7,p=43,q=29,c=394$是已知的(这种情况下都是给出$p,q$的,并且注意到$p-1,q-1$都是$e$的倍数)。然后我们期望的$m$值是$26$(实际上应该是是未知的)。然后我们用下面的代码做一个先加密再解密的实验:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from Crypto.Util.number import *
e,m,p,q=7,26,43,29
n,phi=p*q,(p-1)*(q-1)
'''
print(pow(m,e,n))
print(phi)
'''
c=394
phi=1176
anses=[]
for i in range(n):
if(pow(i,e,n)==c):
anses.append(i)
print(anses)
'''
[18, 26, 73, 114, 155, 157, 163, 200, 201, 244, 276, 287, 288, 308, 327, 329, 331, 374, 416, 421, 491, 501, 503, 534, 566, 577, 588, 636, 675, 679, 706, 714, 722, 781, 824, 851, 867, 878, 888, 972, 975, 996, 1023, 1062, 1146, 1168, 1187, 1230, 1233]
'''

然后我们可以发现:当我们尝试用枚举法(反正数字小)尝试枚举符合条件的答案时,发现一共有多解(并且解的个数恰好是$7^2=49$):我们期望的$26$只是其中的一个解。然而这里也仅仅时在数字较小的时候采用枚举法,我们必须要找到一种办法来真正地来解决这个问题。

0x02 有限域内开根

2o01 Introduction

基础的数学早已告诉我们,$n$次方程有$n$个根。所以当$p-1$和$e$不互素时,$x^e\equiv a \pmod p$要么有$e$个根,要么没有根(这个很容易理解,$e=2$时,方程$x^2\equiv a\pmod p$如果$a$是模$p$二次剩余就有两个根,$a$不是模$p$的二次剩余就没根。)

所以,我们就需要求出在有限域内开$e$次根号,在这里我们无需考虑无解的情况(因为在RSA中,显然有一个解是$m$)

发现$p-1,q-1$都是$e$的 倍数后,我们可以利用sagemath,求出这$e(=7)$个根中的其中一个根,如下图

Picture2o01

至于剩下的$6$个根,我们可以有这样的推导(仍然是以$e=7$为例):$x=(\sqrt[7]{1×x})^7=(\sqrt[7]1)^7×(\sqrt[7]{x})^7$。可能某些无理数在模意义下不存在,但是这没有关系,因为$x^7\equiv 1 \pmod {43}$绝对不止$1$一个根,比如$41^7\equiv 1 \pmod {43}$。我们可以用下面的脚本求出来,原理见Am4dalao博客中的网页链接

2o77Code

代码还是要上一下的,帮助理解,万一真有人看不懂原理呢?(我相信是不存在的)

使用urandom的原因是因为虽然这道题的数字小,但以后的数字可能会很大,并且$\mathrm{get}(x,B)$中的$B$在$x$较大的时候也可以$40$换成更大的数字(例如$400$),如果数字太大可以使用文件输出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
from Crypto.Util.number import *
from os import urandom
def getx(p,B):
x=bytes_to_long(urandom(B))%p
while(x==0):
x=bytes_to_long(urandom(B))%p
return x
#------MAIN BELOW------#
n,p=7,29
assert (p-1)%n==0
rem=n
anses=[]
while rem:
x=getx(p,40)
g=pow(x,(p-1)//n,p)
#print(g,pow(g,2*n,p))
if(pow(g,n*4,p)==1 and g not in anses):
anses.append(g)
rem=rem-1
print(anses)
'''
7th_root_of_1_under_condition_of_n,p=7,43:[35, 4, 41, 16, 21, 11, 1]
7th_root_of_1_under_condition_of_n,p=7,29:[1, 7, 25, 24, 16, 23, 20]
A_7th_root_of_394_under_condition_of_n,p=7,43:7
A_7th_root_of_394_under_condition_of_n,p=7,29:12
'''

我们以$n,p=7,43$的一组解为例:$[35,4,41,16,21,11,1]$一共有七个数字,这七个数字都满足$x^7\equiv 1 \pmod {43}$。然后我们注意一下我们刚才得到的一个数字值$7$。只要我们对这里面的数字每一个都乘上$7$,得到的数列为$[30, 28, 29, 26, 18, 34, 7]$,那么就有了$x^7\equiv394\pmod {43}$,注意到$7^7\equiv 394 \pmod{43}$,因此我们可以姑且地说$\sqrt[7]{394}\equiv 7 \pmod {43}$。$n=7,p=29$的情况也同理。

0x03:求根后两两组合,使用CRT

然后,我们回顾刚才的过程,$m\equiv \sqrt[e]{c} \pmod p,m\equiv \sqrt[e]{c} \pmod q$,一定要注意到由于模数的不同,两个$\sqrt[e]{c}$的值是不一样的,前者我们求出来的$\sqrt[7]{394}$是$[30,28,29,26,18,34,7]$,因为这是模$43$的意义下的数组。后者是模$29$意义下的数组。

然后,我们可以把结果两两组合(组合定律告诉我们一共有$e^2$种方案),下面分别使用sagemath和python做的情况。

3o01:Sagemath截图

3o01p1

3o02 python代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
from Crypto.Util.number import *
def crt2(m1,m2,r1,r2):
M=m1*m2
t1,t2=inverse(m2,m1),inverse(m1,m2)
return (r1*t1*m2+r2*t2*m1)%M
#------MAIN BELOW-----#
s43=[35, 4, 41, 16, 21, 11, 1]
s29=[1, 7, 25, 24, 16, 23, 20]
ans=[]
p43=7
p29=12
for i in range(7):
s43[i]=s43[i]*p43%43
s29[i]=s29[i]*p29%29
print(s43)
print(s29)
for i in s43:
for j in s29:
ans.append(crt2(43,29,i,j))
ans.sort()
print(ans)
'''
s43=[30, 28, 29, 26, 18, 34, 7]
s29=[12, 26, 10, 27, 18, 15, 8]
ans=[18, 26, 73, 114, 155, 157, 163, 200, 201, 244, 276, 287, 288, 308, 327, 329, 331, 374, 416, 421, 491, 501, 503, 534, 566, 577, 588, 636, 675, 679, 706, 714, 722, 781, 824, 851, 867, 878, 888, 972, 975, 996, 1023, 1062, 1146, 1168, 1187, 1230, 1233]
'''

观察观察,是不是最后的结果与我们一开始枚举求解的结果一模一样?(为了观察方便,特此对ans数组排了个序)

0x04: 最后微调,得出答案

当我们得到$49$个解之后,我们可以根据题目的需要,将解筛选出来,因为在真正的CTF比赛中,flag都是有一定格式的,本题中由于仅仅是从数论的方法来讲解,并且数字较小,所以就讲了个方法,筛选是很容易的,YS9X!

0x05: 总结一下知识点

1:解方程$x^e\equiv a \pmod p$,其中$p$为素数,那么当$\gcd(e,p-1)=1$时,该方程有唯一解,为$a^d$,其中$de\equiv 1 \pmod p$。如果$\gcd(e,p-1)\not = 1$,那么方程最多可以有$\gcd(e,p-1)$个解。

2:当$\gcd(e,p-1)\not =1$时。定义方程$x^e\equiv a \pmod p$中,当$a=1$时为齐次有限域指数方程(我自己定义的),当$a\not = 1$时为非齐次有限域指数方程。齐次有限域指数方程的通解(应该说是所有解)可以用上面的python代码直接求出,非齐次有限域指数方程可以利用sagemath求出方程的一个特解$x_0$。然后用$x_0$乘上对应齐次方程的通解,那么就得到了非齐次方程的通解(实际上我刚才说的是一种很不规范的说法,只不过是为了类比线代和高数才这样姑且地定义的)

II- 已知$dp,dq,p,q,c$时求解$m$

0x01

一些过于基础的算式我就不给了,我们可以得到这样的两个式子:$dp\equiv d \pmod {p-1},dq\equiv d \pmod {q-1}$

然后我们可以计算$m_1\equiv c^d \pmod p,m_2\equiv c^d \pmod q$

等式经过变形,可以得到$m_2\equiv (kp+m_1)\pmod p$

然后两边同时减去$m_1$,又有$(m_2-m_1)\equiv kp\pmod p$,即$k\equiv p^{-1}(m_2-m_1) \pmod q$

又因为$m=c^d= kp+m_1$,所以$c^d=(p^{-1}(m_2-m_1)\mod q)×p+m_1$

利用$m_1\equiv c^{dq\mod (q-1)} \pmod q,m_2\equiv c^{dp\mod (p-1)}\pmod p$

就可以直接求出答案了,直接上代码,不多说了。

1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.Util.number import *
import libnum
p =
q =
dp =
dq =
c =
invq=inverse(p,q)
mp=pow(c,dp,p)
mq=pow(c,dq,q)
m=((mp-mq)*invq%p)*q+mq
print(m)

NumberTheory4

huangx607087学习数论的笔记4

1.欧拉$\phi()$函数的性质

任何数$n$的各个因数(包括$1$和自身)的$\phi$值之和等于$n$本身

例如:$15$的因数是$1,3,5,15$,$\phi(1)+\phi(3)+\phi(5)+\phi(15)=1+2+4+8=15$

(只上结论,不讲证明)

2.本原元(原根)

概念:使得$a^e\equiv 1 \pmod p$的最小$e$值为$p-1$的$a$值成为模$p$的本原元。

例如:$2^e\equiv 1 \pmod {11}$成立的最小$e$值为$10$,所以$2$是模$11$的本原元。而$3^e\equiv 1 \pmod {11}$成立的最小$e$值为$5$,所以$3$不是模$11$意义下的本原元。

在模$11$的意义下,我们可以设$\mathrm{ord}(x)$函数,此处有$\mathrm{ord}(2)=10,\mathrm{ord}(3)=5$。当然,如果放在模$7$的意义下,$\mathrm{ord}(2),\mathrm{ord}(3)$的值就分别变成了$3,6$。那么模$7$意义下,$3$就是本原元,$2$不是了。

我们看看在模$11$和模$7$的意义下各个数的$\mathrm{ord}$值

$x$ $\texttt{1}$ $\texttt{2}$ $\texttt{3}$ $\texttt{4}$ $\texttt{5}$ $\texttt{6}$ $\texttt{7}$ $\texttt{8}$ $\texttt{9}$ $\texttt{10}$
$\mathrm {ord}_7(x)$ $\texttt{1}$ $\texttt{3}$ $\texttt{6}$ $\texttt{3}$ $\texttt{6}$ $\texttt{2}$ $\texttt{undef}$ $\texttt{undef}$ $\texttt{undef}$ $\texttt{undef}$
$\mathrm {ord}_{11}(x)$ $\texttt{1}$ $\texttt{10}$ $\texttt{5}$ $\texttt{5}$ $\texttt{5}$ $\texttt{10}$ $\texttt{10}$ $\texttt{10}$ $\texttt{5}$ $\texttt{2}$

对于任意素数$p$来说,总有$\phi(p-1)$个本原元。例如:由于$\phi(10)=4$,所以模$11$的意义下,一共有$4$个本原元,分别是$2,6,7,8$。现在还没有求本原元的有效方法。不过根据表格,我们还可以观察到以下$3$个规律:
1. 任何小于$p$的$\mathrm{ord}$值均为$p-1$的因数
2. 二次剩余一定不是本原元,并且二次剩余的$\mathrm{ord}$值恰好为$\dfrac{p-1}{2}$
3. $\mathrm{ord}(p-1)=2$

COSTAS阵列

COSTAS阵列的性质:构建一个$p-1$阶的方阵,然后要求每行、每列都有一个$1$,其他元素均为$0$。并且任何两个$1$的连线的长度或斜率都不相同。

一般选择一个本源元即可构造一个COSTAS阵列。比如:$5$是模$7$意义下的一个本源元,于是有了序列$5,4,6,2,3,1$。所以我们可以构建一个$6×6$的矩阵$A$

1

存在$k$使得$A^k=E=\mathrm{diag}(1,1,1,1,1,1)$

3.指标(即离散对数)

由$2^9\equiv 5 \pmod {13}$,可以记为$I(5)=9\equiv \dfrac{\ln5}{\ln2} \pmod {13}$

当我们规定底数$a$时,我们可以设$I(x)=\dfrac{\ln x}{\ln a}$的对数形式,该对数的运算与数学上已知的对数形式一模一样。这也是我后面博客里谈到离散对数问题所要考虑到的东西。

我们也可以做个表,设$p=7,a=5$,那么$I(1)$到$I(6)$分别为$6,4,5,2,1,3$。如果我们想要计算$3×5$,我们可以查表得$I(3)=5,I(5)=3,5+3\equiv 1\pmod 7$所以我们可以得到$3×5\equiv1\pmod7$

不过离散对数中得密码学也是个极其难解的问题,后面如果可以,会增加相关推文。

4.二项式定理模$p$扩充

两个结论:
1.$\mathrm{C}_p^k \equiv 0 \pmod p,k \not = 0,p$
2.若$p$为素数,有$(A+B)^p\equiv A^p+B^p \pmod p$

5.Fibonacci数列

一般的Fibonacci数列:$1,1,2,3,5,8,……$,有$F1=F_2=1,F{n}=F{n-1}+F{n-2}$

1.类Fibonacci数列的求通项公式的方法

可以使用矩阵运算:

2

并且这个方法还可以推广到矩阵快速幂的计算上去。

我们可以扩展以下:假如有一个数列$Gn=aG{n-1}+bG_{n-2}$,并给出初值$G_1,G_2$,我们可以构造下面的矩阵。

3

如果想求通项公式,只需要求出最左边矩阵的$2$个特征值$E_1,E_2$,那么通项公式就是$G_n=C_1E_1^n+C_2E_2^n$,带入初值即可求得待定系数。

我们可以继续扩展到三阶矩阵:$Hn=aH{n-1}+bH{n-2}+cH{n-3}$

4

然后同样是求特征值之后用待定系数法利用初值列方程求解。

Fibonacci数列的模$p$周期

对于任意素数,有$T(p^k)=p^{k-1}T(p)$。

$T(2)=3,T(5)=20$是两个特殊值

如果$p\equiv 1 \text8{ or }4 \pmod 5$,那么$T(p)=p$。如果$p\equiv2 \text{ or } 3 \pmod 5$,那么$T(p)=2p+2$

当$a$是合数,$p$是不同的素数时,$a=p_1^{e_1}p_2^{e_2}…p_n^{e_n}$时,$T(a)=T(p_1)T(p_2)…T(p_n)$。

例如:$72=2^3×3^2$,那么有$T(72)=T(2)T(3)=3×8=24$

NumberTheory3

huangx607087 学习数论的笔记3

1.素性测试&卡米歇尔数

由费马小定理可知: $\text{isPrime}(p)=1 \Rightarrow a^{p-1}\equiv 1 \pmod p$

然而:$a^{p-1}\equiv 1 \pmod p \not\Rightarrow \text{isPrime}(p)=1$

卡米歇尔数就是符合$a^{p-1}\equiv 1 \pmod p $并且$ \text{isPrime}(p)=0$的一类数字,最小的数是$561$,$10000$以内的卡米歇尔数一共有$7$个,分别是$561,1105,1729,2465,2821,6601,8911$

卡米歇尔数的性质 设$C$为卡米歇尔数,$p$是$C$的质因数,则$p^2$不整除$C$,并且$p-1$可以整除$C-1$

根据以上的结论,我们不可以用费马小定理判断一个数是否为素数(虽然准确率很高,但还是有错误率的),于是我们可以得到下面的素数性质

素数的的性质 2
如果$p$是素数,那么$p$满足以下$2$个条件之一(设$p-1=2^kq$,其中$q$为奇数)
1.$a^q\equiv 1 \pmod p$
2.$a^q,a^{2q},a^{4q},…,a^{2^{k-1}q}$中至少有一个模$p$结果为$-1\pmod p$

所以,我们就有了以下判断素数的代码,一次误判率低于$0.25$,基本上$30$次的判断准确率就超过了费马小定理了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from random import *
from os import urandom
from Crypto.Util.number import *
def izprime(p):
q=p-1
B=p.bit_length()
K=0
while(q&1==0):
q>>=1
K=K+1
print(q,K)
for i in range(30):
a=bytes_to_long(urandom(B%700))%p
if( pow(a,q,p)==1 or pow(a,q,p)==p-1):
return 1
E=q
for j in range(K):
E=(E*2)%p
if(pow(a,E,p)==p-1):
return 1
return 0
print(izprime(7878787629))

2.二次互反律

二次互反律在 0xGame Div 4 里面有很详细的讲解,这里直接放一下结论。

1: $(\dfrac{a_1a_2}{b})=(\dfrac{a_1}{b})(\dfrac{a_2}{b})$

2:$$(\dfrac{a}{b})= \begin{cases} (\dfrac{b}{a})& a\equiv 1\pmod 4 \text{ or } b\equiv 1\pmod 4\ -(\dfrac{b}{a})& a\equiv 3\pmod 4 \text{ and } b\equiv 3\pmod 4\end{cases}$$

3: $$(\dfrac{-1}{b})= \begin{cases} 1& b\equiv 1\pmod 4\ -1& b\equiv 3\pmod 4\end{cases}$$

4: $$(\dfrac{2}{b})= \begin{cases} 1& b\equiv \text{1 or 7}\pmod 8\ -1& b\equiv \text{3 or 5}\pmod 8\end{cases}$$

程序代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def isqr(x,p):
if p==1 or x==1:
return 1
sgn=1
while x%2==0:
x=x//2
if p%8==3 or p%8==5:
sgn=-sgn
if x<p:
_tmp=p
p=x
x=_tmp
if x%4==3 and p%4==3 :
sgn=-sgn
return sgn*isqr(x%p,p)

3.$p=a^2+b^2?$

结论1:如果某素数$p$可以表示成两个正整数的平方和, 那么$p\equiv 1 \pmod 4$,反过来也同样成立。

下面用递降法求$a,b$:
首先,写$A^2+B^2=Mp,M<p$
然后,选取$u,v$,使得$u\equiv A \pmod p,v\equiv B \pmod p,u,v,\in [\dfrac{-M}{2},\dfrac{M}{2}]$
我们可以得到$u^2+v^2=A^2+B^2\equiv 0 \pmod M$。从而设$u^2+v^2=Mr,A^2+B^2=Mp$
将上面两个式子相乘,得$(u^2+v^2)(A^2+B^2)=M^2rp$
这个式子经过恒等变形,可以化为$(uA+vB)^2+(vA-uB)^2=M^2rp$
两端同时除以$M^2$,就有$\dfrac{(uA+vB)^2+(vA-uB)^2}{M^2}=rp$
可以证明,$r≤\dfrac{M}{2}$,然后继续递降即可。

关于选取$A,B$时需要的注意点: 我们可以取$x^2\equiv -1 \pmod p$,那么有$A=x,B=1,M=\dfrac{A^2+B^2}{p}$
解方程$x^2\equiv -1 \pmod p$时,我们可以随机选取一个数$t$,然后计算$b\equiv t^{\frac{(p-1)}{4}}\pmod p$。又因为$b^2\equiv(\frac{t}{p})\pmod p$。所以$t$总是有$\dfrac{1}{2}$的成功概率。

下面上一下代码,时间复杂度是$O(\ln p)$级别的,$2048$位的质数用时为$2$秒,运行起来还是很快的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
from random import *
from os import urandom
from Crypto.Util.number import *
def getA(p):
assert(p%4==1)
while 1:
t=bytes_to_long(urandom(195))%p
s=pow(t,(p-1)//4,p)
if(pow(s,2,p)==p-1):
return s
def getAns(A,B,M,p):
if(M==1):
return (A,B)
u,v=A%M,B%M
if(u>M//2):
u-=M
if(v>M//2):
v-=M
assert((u**2+v**2)%M==0 and (A**2+B**2)%M==0 )
r=(u**2+v**2)//M
A2=(u*A+v*B)//M
B2=(-u*B+v*A)//M
return getAns(A2,B2,r,p)
#------MAIN BELOW------#
p=getPrime(256)
while(p%4==3):
p=getPrime(256)
A=getA(p)
B=1
assert(A**2+B**2)%p==0
M=(A**2+B**2)//p
Ans,Bns=getAns(A,B,M,p)
Ans,Bns=Ans%p,Bns%p
print('p=',hex(p)[2:])
print('Ans=',hex(Ans)[2:])
print('Bns=',hex(Bns)[2:])
print('The answer is:',(Ans*Ans+Bns*Bns)%p==0)
'''
p= d01bb38ba2700cdbd299f1182d0219cc43a9fd03bcdb9c53b69ea2a38dd3cec1
Ans= e0940478adf7d82d6c27327dbfce631f
Bns= 354b787c45b1c0cf60b30879b3caab70
The answer is: True
'''

RSA Notes 2

huangx607087学习RSA的笔记(2)

O-About

一个密码学废物的学习笔记2,很菜,别看。以后会不定时地补充。

约定:此博客中如果出现除法,未特殊说明的,均为向下取整的整除!

I-RSA的乘法的同态性

0x01 简介和 得到$m$的二进制位数

​ CTF中有些题目会在给出$e,n,c$的情况下,允许你和服务器交互,发送你自己的密文$c’$,然后告诉你有关$c’$解密后的明文的一些高位比特信息。在这种时候,我们就需要用到RSA乘法具有同态性的这一特殊性质,那么什么是RSA的同态性呢?

​ 我们已经知道,RSA加密函数$c=E(m) \equiv m^e \mod n$。其中$(e,n,c)$作为公钥,都是已知的。不过我们可以推导一下这样的公式:$E(2m)\equiv 2^em^e\equiv 2^e c\mod n$。所以如果在获得对个人密文的解密权的时候,我们就可以通过向服务器发送$2^e c$,这一就可以获得$2m$的值。同理,我们可以发送$2^{ke}c$,得到的解密结果就是$2^{k}m$。所以运行以下代码,我们得到的结果是$(12,24,48,96)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.Util.number import *
m=12
p=getPrime(512)
q=getPrime(512)
n=p*q
e=65537
d=inverse(e,(p-1)*(q-1))
c=pow(m,e,n)
print(c)
c2,c3,c4=c*pow(2,e,n)%n,c*pow(2,2*e,n)%n,c*pow(2,3*e,n)%n
print(c2)
m1,m2,m3,m4=pow(c,d,n),pow(c2,d,n),pow(c3,d,n),pow(c4,d,n)
print(m1,m2,m3,m4)

​ 这种方法我们可以确定明文的长度:假如$n$是$2048$位,每次给你最高$8$位,那么被隐藏了$2040$位。假如我们一共移动了$740$位发现高位不再为$0$,那么我们可以确定明文长度为$2040-740=1300$位二进制数。

0x02 RSA确定$m$位数后确定明文$m$的值

​ 假如我们以上面那个为例子,我们确定了明文是$1300$位二进制数,那么我们现在就可以二分了:我们可以设置$L=2^{739},R=2^{740}$进行二分操作。

​ 注意在RSA中,有一个很神奇的式子:
$$
(pm)^e \equiv cp^e \mod n
$$

​ 然后我们可以得到这样的方程:$I=\dfrac {2^{2040}}{m}∈[2^{739},2^{740}]$,也就是$I \in [2×2^{738},4×2^{738}]$。对服务器发送区间中值$M=3×2^{738}$的加密结果乘上$c$的值,如果服务器告诉你最高的$8$位二进制数值不为$0$,则说明我们发送的数字偏大,随后我们就可以换区间右边界$R$为这一次的中值$M$,区间变成$[4×2^{737},6×2^{737}]$。若最后告诉你结果为$0$,那么说明我们发送的值偏小,然后我们可以把左边界换成$M$,然后把区间换成$[6×2^{737},8×2^{737}]$。后面以此类推。

​ 然而,我发现:自己的取值出了一个严重的问题,下面是一次二分过后的运行结果:

2

​ 分析了一下,原因很简单:因为这个时候除数是$2^{739}$到$2^{740}$左右的数量级,被除数是$2^{2040}$数量级,相差过大,于是我重新造数据:把flag的数量级降低到$2^{400}$,二分的$L,R$数量级提升到$2^{1640}$

​ 这一次的的运行结果,很准确:

2

​ 做了几次实验,发现flag规模在$2^{1000}$以下的时候无误差,$2^{1050}$规模的flag有不超过$10$的误差,$2^{1100}$规模的flag有几百的误差,$2^{1200}$的flag有几十万的误差,$2^{1300}$的flag的误差比特已经接近总比特数的一半。目测如果flag在$\sqrt{n}$内的话,就不会出现误差值。

最后贴一下测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
from Crypto.Util.number import *
import random
def GetNumberBitz(x):
s=0
while 1:
tmp=random.randint(0,255)
s=s*256+tmp
if(s>(1<<5000)):
break
s=s%(1<<(x+1))
while(s.bit_length()!=x):
s=GetNumberBitz(x)
return s
def GenerateKey(B):
e,p,q=getPrime(random.randrange(16,20)),getPrime(B//2),getPrime(B//2)
n,phi=p*q,(p-1)*(q-1)
d=inverse(e,phi)
return e,n,d
def judg(CC,D,N):
x=pow(CC,D,N)
st=long_to_bytes(x,2048//8)
if(st.startswith(b"\x00")):
return 1
else:
return 0
def Attack(E,N,C,D,B,T):
L,R=2**(B),2**(B+1)
while R-L>1:
if(R-L).bit_length()%50==0:
print(hex(L),hex(R))
M=(L+R)//2
CC=(pow(M,E,N)*C)%N
check=judg(CC,D,N)
if(check==1):
L=M
else:
R=M
return L
#----main below----#
flag=GetNumberBitz(400)
assert flag.bit_length()==400
e,n,d=GenerateKey(2048)
while n.bit_length()!=2048:
e,n,d=GenerateKey(2048)
c=pow(flag,e,n)
print('e=',e)
print('n=',n)
print('c=',c)
print('2**2040//flag=',hex(2**2040//flag))
F=Attack(e,n,c,d,2040-400,2040)
print(hex(2**2040//F))
print(hex(2**2040//(F+1)))
print(hex(flag))

0x03 最后一个比特位泄露破解的原理(摘自CTFWIKI,本废物还不懂)

​ 假设目前存在一个 Oracle,它会对一个给定的密文进行解密,并且会给出明文的最后一个字节。那么给定一个加密后的密文,我们只需要 $\log_{256}n$ 次就可以知道这个密文对应的明文消息。

这个其实算作 RSA parity Oracle 的扩展,既然可以泄露出最后一个字节,那么按道理我们获取密文对应明文的次数应该可以减少。

假设$C=P^e \bmod N$

第一次时,我们可以给服务器发送$C*256^e=(256P)^e \bmod N$

服务器会计算得到$256P \bmod N$

这里

  • $256P$ 是偶数。
  • $N$ 是奇数,因为它是由两个大素数相乘得到。

由于 $P$ 一般是小于$ N$ 的,那么$256P \bmod N=256P-kn, k<256$。而且对于两个不同的 $k_1,k_2$,我们有

$256P-k_1n \not\equiv 256P-k_2n \bmod 256$

我们可以利用反证法来证明上述不等式。同时 $256P-kn$ 的最后一个字节其实就是 $-kn$ 在模 $256$ 的情况下获取的。那么,其实我们可以首先枚举出 $0$~$255 $情况下的最后一个字节,构造一个 k 和最后一个字节的映射表 map

当服务器返回最后一个字节 b,那么我们可以根据上述构造的映射表得知 $k$,即减去了 $k$ 个$N$, 即 $kN \leq 256 P \leq (k+1)N$。

此后,我们使用数学归纳法来获取 P 的范围,即假设在第 i 次时,$\dfrac{xN}{256^{i}} \leq P < \dfrac{xN+N}{256^{i}}$

进一步,在第 i+1 次时,我们可以发送

$C*256^{(i+1)e}$

服务器会计算得到

$256^{i+1}P \bmod N=256^{i+1}P-kN$

$0 \leq 256^{i+1}P-kN<N$

$\dfrac{kN}{256^{i+1}} \leq P < \dfrac{kN+N}{256^{i+1}}$

根据第 $i$ 次的结果

$\dfrac{256xN}{256^{i+1}} \leq P < \dfrac{256xN+256N}{256^{i+1}}$

我们这里可以假设 k=256y+t, 而这里的 t 就是我们可以通过映射表获取的。

$\dfrac{256yN+tN}{256^{i+1}} \leq P < \dfrac{256yN+(t+1)N}{256^{i+1}}$

与此同时,由于 P 必然存在,所以第 i+1 得到的这个范围和第 i 次得到的范围必然存在交集。

所以 y 必然与 x 相等。

进一步我们可以这么归纳,初始情况下

1
2
lb = 0
ub = N

假设服务器返回了 b,那么

1
2
3
4
k = mab[b]
interval = (ub-lb)//256
lb = lb + interval * k
ub = lb + interval

II-关于一些特殊性质的$n$的因数分解

0x01 $n$的值小于$512$位二进制数

​ 可以用yafu或者sagemath直接分解,一般$30$分钟内就可以分解成功

0x02 $p,q$ 是两个相邻的素数

​ 这种方法是非常简单的,我们只需要用gmpy2中的iroot函数直接取整开根。然后设$q$是$\sqrt n$的下一个素数,然后我们就可以得到$p$的值了,进而成功分解$n$

0x03 $|p-q|$过大或者过小的分解

​ $|p-q|$过大的时候,可以直接通过枚举法确定其中一个因数

​ $|p-q|$过小的时候:由基本的平方差公式,有:
$$
\dfrac{(p+q)^2}{4}-n=\dfrac{(p+q)^2}{4}-pq=\dfrac{(p-q)^2}{4}
$$
​ 既然 $|p-q|$较小,那么 $\dfrac{(p-q)^2}{4}$ 自然也比较小,进而 $\dfrac{(p+q)^2}{4}$ 只是比 N 稍微大一点,所以 $\dfrac{p+q}{2}$ 与 $\sqrt{n}$ 相近。

​ 此时我们可以检查$\sqrt n$的每一个整数$x$,知道找到一个$x$使得$x^2-n$是平方数,记作$y^2$。然后根据平方差公式可以分解$n$

0x04 $p-1$光滑(摘自yulige的博客–NCTF2019题解)

0o401 什么是光滑数

​ 首先引入光滑数的定义:若一个数的所有素因子都不超过$B$,那么称这个数为$B$光滑数,例如:由于$72=3^2×2^3$,所有的素因子都不超过$3$,所以$72$是$3$光滑数,当然也是$5,7,11,…$光滑数。

0o402 Pollards $p-1$ 算法

​ 这个时候我们可以使用Pollard’s $p − 1$ 算法来分解 $n$,具体原理如下:

​ 由费马小定理$a^{p-1} – 1 \equiv 0 \mod \ p$可知,$a^{p-1} – 1$ 是 $p$ 的倍数,也就可以认为是$a^{t(p-1)} – 1 =k p$,其中$t,p\in N_+$。因此,简单地观察就可以知道,如果指数$\text{exp}$是 $p-1$ 的倍数,那么$a^\text{exp} – 1 $就会是 $p$ 的倍数。所以,我们只需要找到一个$\text{exp}$使得$a^\text{exp}$是$p$的倍数的时候,那么我们计算$\gcd(a^{\text{exp}},n)$,就可以得到结果,而这个结果就是$p$,所以,这里的关键就是寻找这个合适的$\text{exp}$值。

Pollard的厉害之处就在于此,他发现,如果p-1正好是一些很小的质数的乘积,那么p-1就能整除$n!$,其中$n$是一个不太大的数。假设p-1p1, p2, ..., pk这些质数的乘积,其中最大的质数是pk。那么,很显然pk!=1·2·...·pk肯定包括了p1, p2, ..., pk这些质数的乘积,pk!肯定是p-1的倍数。

​ 也就是说,$n > pk$ 的时候,$n!$很大概率上就能被p-1整除。(考虑到p1, p2, ..., pk中可能有重复的情况)

​ 这导致了Pollard' p-1 method

​ 对于每一个$n = 2, 3, 4, …$,我们任意选择一个底数$a$(事实上,我们可以简单地选择为$2$),并计算
$$
gcd(a^{n!-1}, N)
$$
​ 如果结果落在1和$n$中间,那么我们就成功了。

​ 当然,这里的所有操作都可以在模$N$的操作下进行,也就是计算$a^{n!-1}\ \text{mod}\ N$。并且,我们也不必计算每一个数字,选择一个恰当的间隔(比如$15$)计算可以减少耗时

0o477 代码实现

​ 我们可以上一下代码:这里的的$N$是$104729$光滑的(因为$104729$刚好是第$10000$个素数)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from Crypto.Util.number import *
def Pollard_p_1(N):
a = 2
while True:
f = a
# precompute
for i in range(1, 80000):
f = pow(f, i, N)
for i in range(80000, 104729+1):
f = pow(f, i, N)
if i % 15 == 0:
d = GCD(f-1, N)
if 1 < d < N:
return d
print(a)
a += 1

0x05 $p+1$光滑(即$p+1=db^2|_{d<256,\text{isPrime}(d)=\text{True}}$)

​ 这种情况下,我们可以使用William $p+1$算法

0o501 理论基础

​ 从标题中我们可以知道:如果$p+1=db^2$ 的话,我们可以考虑分解$n$的值。而这实际上基于这样一个理论基础:如果$n=pm$,并且$p$是素数,并且如果$4p$可以写成集合{$ 3b^2+1,11b^2+1,19b^2+1,43b^2+1,67b^2+1,163b^2+1$} ,其中${b\in N_+}$ 中的任意一个形式,那么我们可以在$\ln n$的复杂度里找到$p$的真实值。

​ 算法的原理太复杂,这里就不多讲了,直接看代码吧(

0o577 算法代码

​ 最后贴一下代码,$\text{Sagemath 9.1 Notebook}$中的代码,摘自$\text{NCTF 2020 WP}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def qicheng(n: int):
R = Integers(n)
js = [0, (-2 ^ 5) ^ 3, (-2 ^ 5*3) ^ 3, (-2 ^ 5*3*5*11) ^ 3, (-2 ^ 6*3*5*23*29) ^ 3]
p, q = None, None
for _ in range(20):
for j in js:
if j == 0:
a = R.random_element()
E = EllipticCurve([0, a])
else:
a = R(j)/(R(1728)-R(j))
c = R.random_element()
E = EllipticCurve([3*a*c ^ 2, 2*a*c ^ 3])
x = R.random_element()
z = E.division_polynomial(n, x)
g = gcd(z, n)
if g > 1:
p = Integer(g)
q = Integer(n)//p
break
if p:
break
return (p, q)
print(qicheng(1444329727510154393553799612747635457542181563961160832013134005088873165794135221))
#(74611921979343086722526424506387128972933, 19357894679486057806987068960980789709937)

0x06 Pollord Rho算法(时间复杂度$O(\sqrt[4]{n})$)

0o601 算法介绍

​ 这个算法的核心思想就是猜一个数,看看是否为$x$的因数。

​ 我们可以随机地选取两$v,t$个数,然后根据$v=v_{i-1}^2+t \mod x$ ,这样就会构成一个环。然后在循环内部猜测。即可。

​ 代码实现原理也比较复杂(实际上是因为懒,博客写到后面也很累的),自己百度吧。上一个是百度不到的。23333

0o677 代码实现(自己打的代码,Python常数较大,能过洛谷模板题93分)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
from Crypto.Util.number import *
from random import *
A=0
def culc(x,c,n):
return (x*x+c)%n
def PollardRho(x):
s,t,goal,val=0,0,1,1
c=getrandbits(15)%(x-1)+1
while 1:
for det in range(1,goal+1):
t=culc(t,c,x)
val=val*abs(t-s)%x
if(det%127==0):
d=GCD(val,x)
if(d>1):
return d
d=GCD(val,x)
if(d>1):
return d
goal*=2
s=t
val=1
def factor(x):
global A
if(x<=A or x<2):
return
if(isPrime(x)):
A=max(A,x)
return
p=x
while(p>=x):
p=PollardRho(x)
while((x%p)==0):
x//=p
factor(x)
factor(p)
T=int(input())
while T>0:
T-=1
A=0
a=int(input())
if(isPrime(a)):
print('Prime')
else:
factor(a)
print(A)

UNCTFwp

huangx607087对于UNCTF密码学的笔记

About

在队伍里dxgdl的同意下,又水了一篇题解,然而有两道最难的题目我不会写,Hermes大佬却已经把7条密码学AK了,我果然是个fw

Write Ups

1.RSA1

首先先看一下题目代码:(最后给出部分略)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from Crypto.Util import number
import gmpy2
from Crypto.Util.number import bytes_to_long

p = number.getPrime(1024)
q = number.getPrime(1024)
if p > q:
a = p + q
b = p - q
print(a,b)

n = p * q
e = 65537
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
m = bytes_to_long(b'msg')
c = pow(m,e,n)
print(c)

题目给出了$a,b$的值,还有加密后密文$c$的值,很容易地我们可以求出来$p=(a+b)/2,q=(a-b)/2$.然后直接用RSA的最基本的方法解决即可,很水的一道题。

2.(大法官之失去的营养怎么补)

这道题一开始给出了一个长为$100$的字符串如下:ottttootoootooooottoootooottotootttootooottotttooootttototoottooootoooottotoottottooooooooottotootto。然后我们可以看到,这个字符串里面只有ot两个字符,盲猜o是one,t是two。

然后观察到密文长度刚好是$100$,符合条件长度是$5$的倍数,可以考虑培根密码。把o替换成At替换成B。然后随便找个网站就可以解出题目了。

3. EZRSA

又是一道RSA的题目,题目给出了$e,n,c$数值,我们可以看到$\ln e ≈ \ln n $。自然会想到winnerattack的方法。(之前Am473ur师傅出的那道题是直接爆破$d$,可能是因为$d$的值太小了导致我一重$for$循环直接枚举出来,没有对其进行深刻研究233333)。

不多说,直接上解题代码,也就是winnerattack的脚本。到时候我会更新一下自己的RSA笔记。

这个脚本是在网上找到的,不是自己打的= =所以可以证明我的fw属性成立

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
from __future__ import print_function
import libnum

def continued_fractions_expansion(numerator,denominator):#(e,N)
result=[]

divident = numerator % denominator
quotient = numerator // denominator
result.append(quotient)

while divident != 0:
numerator = numerator - quotient * denominator

tmp = denominator
denominator = numerator
numerator = tmp

divident = numerator % denominator
quotient = numerator // denominator
result.append(quotient)

return result

def convergents(expansion):
convergents=[(expansion[0], 1)]
for i in range(1, len(expansion)):
numerator = 1
denominator = expansion[i]
for j in range(i - 1, -1, -1):
numerator += expansion[j] * denominator
if j==0:
break
tmp = denominator
denominator = numerator
numerator = tmp
convergents.append((numerator, denominator)) #(k,d)
return convergents

def newtonSqrt(n):
approx = n // 2
better = (approx + n // approx) // 2
while better != approx:
approx = better
better = (approx + n // approx) // 2
return approx

def wiener_attack(cons, e, N):
for cs in cons:
k,d = cs
if k == 0:
continue
phi_N = (e * d - 1) // k
#x**2 - ((N - phi_N) + 1) * x + N = 0
a = 1
b = -((N - phi_N) + 1)
c = N
delta = b * b - 4 * a * c
if delta <= 0:
continue
x1 = (newtonSqrt(delta) - b)//(2 * a)
x2 = -(newtonSqrt(delta) + b)//(2 * a)
if x1 * x2 == N:
return [x1, x2, k, d]

if __name__ == "__main__":
n = 147282573611984580384965727976839351356009465616053475428039851794553880833177877211323318130843267847303264730088424552657129314295117614222630326581943132950689147833674506592824134135054877394753008169629583742916853056999371985307138775298080986801742942833212727949277517691311315098722536282119888605701
e = 18437613570247445737704630776150775735509244525633303532921813122997549954741828855898842356900537746647414676272022397989161180996467240795661928117273837666615415153571959258847829528131519423486261757569454011940318849589730152031528323576997801788206457548531802663834418381061551227544937412734776581781

c = 140896698267670480175739817539898638657099087197096836734243016824204113452987617610944986742919793506024892638851339015015706164412994514598564989374037762836439262224649359411190187875207060663509777017529293145434535056275850555331099130633232844054767057175076598741233988533181035871238444008366306956934

expansion = continued_fractions_expansion(e, n)
cons = convergents(expansion)
p, q, k, d = wiener_attack(cons, e, n)
m = pow(c, d, n)
print(libnum.n2s(m))

4

一道没有任何技术含量的题目,只需要打开Word文档,把字体调成Wingdings 2。然后看着图片一个一个对照就可以了(最后转成正常的字体(比如宋体)

5 SignIn

先看一下题目代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import random
from Crypto.Cipher import AES
from os import urandom
from string import printable
from binascii import hexlify
from secret import flag

random.seed(urandom(32))

key1 = '0'*13 + ''.join([random.choice(printable) for _ in range(3)])
key2 = ''.join([random.choice(printable) for _ in range(3)]) + '0'*13

cipher1 = AES.new(key=key1.encode(), mode=AES.MODE_ECB)
cipher2 = AES.new(key=key2.encode(), mode=AES.MODE_ECB)

pt = input("You have a chance to get something: ")
pt = pt.encode()

val = len(pt) % 16
if not val == 0:
pt += b'\x00'*(16 - val)

c1 = cipher1.encrypt(pt)
c2 = cipher2.encrypt(c1)
print('Your cipher:{}'.format(hexlify(c2)))

assert(len(flag) % 16 == 0)
c3 = cipher1.encrypt(flag)
c4 = cipher2.encrypt(c3)
print('Your flag:{}'.format(hexlify(c4)))
'''
You have a chance to get something: UNCTF2020_Enjoy_Crypto~
Your cipher:b'01a4e429e76db218fa0eb18f03ec69c9200a2362d8b4d7ea46170ce698389bbd'
Your flag:b'196cc94c2d685beb54beeaa14c1dc0a6f3794d65fca0d1a1274515166e4255ab367383092e42d774992f74bc138faaad'
'''

题目给出了一次加密的结果。从代码中我们可以看到:$key1$的前$13$位密钥全是$0$,后$3$位是未知的。而$key2$的前$3$位是未知的,后面$13$位全是$0$。

第一次对给出的内容加密,我们可以看到第一次加密的结果是$c1$,第二次加密的结果是$c2$。并且$c2$是已知的。考虑到字符库是有限的(只有$100$个可用字符)。所以我们可以暴力枚举所有$100^3=1000000$种$pt$的加密可能,然后暴力枚举$1000000$种对$p2$解密的可能性,换句话说,我们就通过两面夹击的方式,枚举到了两种不同途径$c1$的可能结果。然后我们就可以寻找到相同的部分,就能得到$c1$字符串了。

暴力枚举代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
from string import *
from gmpy2 import *
from Crypto.Util.number import *
from Crypto.Cipher import AES
pt=b"UNCTF2020_Enjoy_Crypto~"
val = len(pt) % 16
if not val == 0:
pt += b'\x00'*(16 - val)
print(pt)
s=printable
GivenChiper='01a4e429e76db218fa0eb18f03ec69c9200a2362d8b4d7ea46170ce698389bbd'
GivenChiper=long_to_bytes(int(GivenChiper,16))
Key1='0'*13
boxi=[]
for i1 in s:
for i2 in s:
for i3 in s:
Keyi=Key1+i1+i2+i3
cipher1 = AES.new(key=Keyi.encode(), mode=AES.MODE_ECB)
f=cipher1.encrypt(pt)
boxi+=[f]
with open('data1.out', 'w') as f:
#for i in range(10):
for i in range(len(s)**3):
if(i%25000==0):
print(i)
f.write(hex(bytes_to_long(boxi[i]))[2:]+'\n')
Key2='0'*13
boxi=[]
for i1 in s:
for i2 in s:
for i3 in s:
Keyii=i1+i2+i3+Key2
cipher2 = AES.new(key=Keyii.encode(), mode=AES.MODE_ECB)
f=cipher2.decrypt(GivenChiper)
boxi+=[f]
with open('data2.out', 'w') as f:
for i in range(len(s)**3):
if(i%25000==0):
print(i)
f.write(hex(bytes_to_long(boxi[i]))[2:]+'\n')

然后我们就出来了data1和data2两个文件,然后我们用以下的C++脚本,可以找到唯一的共同输出(这样我们可以用$O(2n)$的复杂度,而不是魔鬼般的$O(n^2)$)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
map<string,bool>p;
string s;
int main()
{
int i,j;
freopen("data2.out","r",stdin);
for(i=1;i<=1000000;i++)
{
cin>>s;
p[s]=1;
}
freopen("data1.out","r",stdin);
for(i=1;i<=1000000;i++)
{
cin>>s;
if(p[s]==1)
cout<<s<<endl;
}
return 0;
}

然后我们再一次暴力枚举,找出共同点时的密钥$k1$和$k2$被省略的$3$位数。

找到之后,我们就可以用以下脚本,解出flag了(

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from Crypto.Cipher import AES
from os import urandom
from string import printable
from binascii import hexlify
from Crypto.Util.number import *
key1 = '0'*13 +'W<&'
key2 = '0/i' + '0'*13
C=b'196cc94c2d685beb54beeaa14c1dc0a6f3794d65fca0d1a1274515166e4255ab367383092e42d774992f74bc138faaad'
C=long_to_bytes(int(C,16))
print(C)
cipher1 = AES.new(key=key1.encode(), mode=AES.MODE_ECB)
cipher2 = AES.new(key=key2.encode(), mode=AES.MODE_ECB)
D=cipher2.decrypt(C)
D=cipher1.decrypt(D)
print(D)