RSA Notes 3

huangx607087学习RSA的笔记(3)

O-About

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

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

I-RSA中$gcd(\varphi ,e)\ne 1$的情况

0x01 题目背景&引例

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

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

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

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]
'''
PYTHON

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

0x02 有限域内开根

2o01 Introduction

基础的数学早已告诉我们，$$次方程有$$个根。所以当$$和$$不互素时，$$要么有$$个根，要么没有根（这个很容易理解，$$时，方程$$如果$$是模$$二次剩余就有两个根，$$不是模$$的二次剩余就没根。）

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

发现$$都是$$的 倍数后，我们可以利用sagemath，求出这$$个根中的其中一个根，如下图

Picture2o01

至于剩下的$$个根，我们可以有这样的推导（仍然是以$$为例）：$$。可能某些无理数在模意义下不存在，但是这没有关系，因为$$绝对不止$$一个根，比如$$。我们可以用下面的脚本求出来，原理见Am4dalao博客中的网页链接

Upd 2021.1.17

用以下sagemath代码求特解更快（$$的情况下）

import random
def AMM(o, r, q):
    print('\n----------------------------------------------------------------------------------')
    print('Start to run Adleman-Manders-Miller Root Extraction Method')
    print('Try to find one {:#x}th root of {} modulo {}'.format(r, o, q))
    g = GF(q)
    o = g(o)
    p = g(random.randint(1, q))
    while p ^ ((q-1) // r) == 1:
        p = g(random.randint(1, q))
    print('[+] Find p:{}'.format(p))
    t = 0
    s = q - 1
    while s % r == 0:
        t += 1
        s = s // r
    print('[+] Find s:{}, t:{}'.format(s, t))
    k = 1
    while (k * s + 1) % r != 0:
        k += 1
    alp = (k * s + 1) // r
    print('[+] Find alp:{}'.format(alp))
    a = p ^ (r**(t-1) * s)
    b = o ^ (r*alp - 1)
    c = p ^ s
    h = 1
    for i in range(1, t):
        d = b ^ (r^(t-1-i))
        if d == 1:
            j = 0
        else:
            print('[+] Calculating DLP...')
            j = - dicreat_log(a, d)
            print('[+] Finish DLP...')
        b = b * (c^r)^j
        h = h * c^j
        c = c ^ r
    result = o^alp * h
    return result
print(1)
p=
q=
n=p*q
c=
phi=(p-1)*(q-1)
cMp=c%p
cMq=c%q
print(AMM(cMp,4919,p))
print(AMM(cMq,4919,q))

PYTHON

2o77Code

代码还是要上一下的，帮助理解，万一真有人看不懂原理呢？（我相信是不存在的）

使用urandom的原因是因为虽然这道题的数字小，但以后的数字可能会很大，并且$$中的$$在$$较大的时候也可以$$换成更大的数字（例如$$），如果数字太大可以使用文件输出。

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
'''
PYTHON

我们以$$的一组解为例：$$一共有七个数字，这七个数字都满足$$。然后我们注意一下我们刚才得到的一个数字值$$。只要我们对这里面的数字每一个都乘上$$，得到的数列为$$,那么就有了$$，注意到$$，因此我们可以姑且地说$$。$$的情况也同理。

0x03：求根后两两组合，使用CRT

然后，我们回顾刚才的过程，$$，一定要注意到由于模数的不同，两个$$的值是不一样的，前者我们求出来的$$是$$，因为这是模$$的意义下的数组。后者是模$$意义下的数组。

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

3o01：Sagemath截图

3o01p1

3o02 python代码

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]
'''

PYTHON

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

0x04： 最后微调，得出答案

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

0x05： 总结一下知识点

1：解方程$$，其中$$为素数，那么当$$时，该方程有唯一解，为$$，其中$$。如果$$，那么方程最多可以有$$个解。

2：当$$时。定义方程$$中，当$$时为齐次有限域指数方程（我自己定义的），当$$时为非齐次有限域指数方程。齐次有限域指数方程的通解（应该说是所有解）可以用上面的python代码直接求出，非齐次有限域指数方程可以利用sagemath求出方程的一个特解$$。然后用$$乘上对应齐次方程的通解，那么就得到了非齐次方程的通解（实际上我刚才说的是一种很不规范的说法，只不过是为了类比线代和高数才这样姑且地定义的）。

II- 已知$$时求解$$

0x01

一些过于基础的算式我就不给了，我们可以得到这样的两个式子：$$

然后我们可以计算$$

等式经过变形，可以得到$$

然后两边同时减去$$，又有$$，即$$

又因为$$，所以$$

利用$$

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

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)

PYTHON