ACTF2022

impossible RSA

from Crypto.PublicKey import RSA
from Crypto.Util.number import *
import gmpy2
e = 65537
with open("C:\\Users\\Haier\\Downloads\\impossibleRSA\\public.pem","rb") as file:
    rsa = RSA.import_key(file.read())
    n = rsa.n
# print(n)
with open("C:\\Users\\Haier\\Downloads\\impossibleRSA\\flag","rb") as file:
    c = bytes_to_long(file.read())
# print(c)
a = e*n
# print(gmpy2.iroot(4,2))
for i in range(1,e):
    L = gmpy2.iroot(1+4*i*a,2)
    if L[1]:
        p = (L[0]-1)//(2*i)
        break
q = n//p
d = gmpy2.invert(e,(p-1)*(q-1))
m = pow(c,d,n)
print(long_to_bytes(m))
# b'ACTF{F1nD1nG_5pEcia1_n_i5_nOt_eA5y}'

Rsa LEAK

1. random_prime(n,proof=None,lbound=2) 该函数返回一个随机数 介于 lbound 和 n 之间，即从小于或等于n的素数集中随机选择返回的素数p。

​

PS:SegeMath使用指南https://blog.csdn.net/UN_spoken/article/details/102490953

• 中间相遇攻击

  中间相遇思想------以空间换时间

dic = {}
for i in tqdm(range(1,2**24)):
    tmp = (b - pow(i,e,n))%n
    dic[tmp] = i
for i in tqdm(range(2**24)):
    t = pow(i,e,n)
    if t in dic.keys():
        print(i,dic[t])
        break
#rp = 405771
#rq = 11974933

• 对于n=pp.qq，不难发现a.b就等于n开四次根取整，证明如下（rp和rq对于a和b来说相当于一个很小的量）：

• 整理一下所有的已知条件：

  rp=pp−p

  rq=qq−q

  p∗q=(ab)^4

  pp∗qq=n

  如果我们用rp乘rq，会出现n,pp.q,pp.q,p.q ，由于 pp.qpp.q 是未知的，所以需要构造这个来相消；因此考虑 rp.qq，同理rq.pp，消去以后剩下 p.q 和 n ，都是已知量，最后得到：

  

  image-20220706022132661

  等式两边同乘qq得到关于qq的一元二次方程，解出来就是qq，完整过程：

import gmpy2
from tqdm import tqdm
from Crypto.Util.number import long_to_bytes
# a = 0xdeadbeef
# print(a)
# print((pow(rp,e,n)+pow(rq,e,n))%n == b)
# b = 90846368443479079691227824311356359506
# # print(b)
# e = 65537
# n = 122146249659110799196678177080657779971
# dic = {}
# for i in tqdm(range(1,2**24)):
#     tmp = (b - pow(i,e,n))%n
#     dic[tmp] = i
# for i in tqdm(range(2**24)):
#     t = pow(i,e,n)
#     if t in dic.keys():
#         print(i,dic[t])
#         break
rp = 11974933
rq = 405771

#sege
n = 3183573836769699313763043722513486503160533089470716348487649113450828830224151824106050562868640291712433283679799855890306945562430572137128269318944453041825476154913676849658599642113896525291798525533722805116041675462675732995881671359593602584751304602244415149859346875340361740775463623467503186824385780851920136368593725535779854726168687179051303851797111239451264183276544616736820298054063232641359775128753071340474714720534858295660426278356630743758247422916519687362426114443660989774519751234591819547129288719863041972824405872212208118093577184659446552017086531002340663509215501866212294702743
e = 65537
c = 48433948078708266558408900822131846839473472350405274958254566291017137879542806238459456400958349315245447486509633749276746053786868315163583443030289607980449076267295483248068122553237802668045588106193692102901936355277693449867608379899254200590252441986645643511838233803828204450622023993363140246583650322952060860867801081687288233255776380790653361695125971596448862744165007007840033270102756536056501059098523990991260352123691349393725158028931174218091973919457078350257978338294099849690514328273829474324145569140386584429042884336459789499705672633475010234403132893629856284982320249119974872840
# t = gmpy2.iroot(n,4)[0]**4
# print(t)
t = 3183573836769699313763043722513486503160533089470716348487649113450828830224151824106050562868640291712433283679799855890306945562430572137128269318944453041825476154913676849658599642113896525291798525533722805116041675462675732995881671359593602584751304602244415149859346875340361740775463623467502328920464595944875823756019648351596914354572401402251876527802445435468015080936376618513513552460965936940576274710339733292071011277445826811936493865285518787312365283313906991771609447176865489740193258576514631696581798918138765169132954278679508175003271322897471002162853326131519571176643755758578383261696
A = rp
B = t - rp*rq - n
C = rq*n
delte = gmpy2.iroot(B**2-4*A*C,2)[0]
p = (-B + delte )//(2*A)
q = n//p
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
m = pow(c,d,n)
print(long_to_bytes(m))
# b'ACTF{lsb_attack_in_RSA|a32d7f}'