[Crypto学习笔记] 简单的RSA类题目

15 分钟阅读时长

发布时间： November 13, 2024

有一段时间我在进行反思, 受以前的一些经历限制, 一直以来是跳跃性地学习密码学, 以至于一边在忙着一些复杂的东西, 但又有很多基本概念实际上并没有搞懂, 所以后来有了些想法, 决定比较系统地梳理一下知识点.

前置概念

rsa原理

从最基本的rsa开始, 标准题目中可以分解n为p, q构造phin获取私钥:

gcd

即求取多个数的最大公因数, 考虑到数可以由一个或多个素数相乘构成, 在多个数中共同构成的素数乘积即为最大公因数, 基本数学概念, 以下举个简单例子:

from math import gcd

a = 7 * 11 * 3 * 2
b = 7 * 11 * 5
c = 7 * 11

print(gcd(a,b) == c)
# True

可以通过辗转相除法获取最大公因数.

hgcd

全称Half-GCD, 在多项式中取gcd的一种算法, 多项式同样可以分解为一个或多个多项式, 相比较直接gcd, hgcd在取模运算上做了优化, 想象有项数极高的两个多项式, 在最坏情况下每次辗转相除可以消去一项, 实际上在整除过程中往往只需要在高次项就可以计算出答案, 但是取模需要精度计算到最后, 造成了计算资源浪费. 考虑存在以下两个多项式¹:

$\color{#FF0000}但是我真的写不动了, 所以决定以后再说.$

\[\begin{matrix} f(x) \\ g(x) \end{matrix}\]

以下偷取一段Half-GCD的代码进行分析:

def HGCD(a, b):
    if 2 * b.degree() <= a.degree() or a.degree() == 1:
        return 1, 0, 0, 1
    m = a.degree() // 2
    a_top, a_bot = a.quo_rem(x^m)
    b_top, b_bot = b.quo_rem(x^m)
    R00, R01, R10, R11 = HGCD(a_top, b_top)
    c = R00 * a + R01 * b
    d = R10 * a + R11 * b
    q, e = c.quo_rem(d)
    d_top, d_bot = d.quo_rem(x^(m // 2))
    e_top, e_bot = e.quo_rem(x^(m // 2))
    S00, S01, S10, S11 = HGCD(d_top, e_top)
    RET00 = S01 * R00 + (S00 - q * S01) * R10
    RET01 = S01 * R01 + (S00 - q * S01) * R11
    RET10 = S11 * R00 + (S10 - q * S11) * R10
    RET11 = S11 * R01 + (S10 - q * S11) * R11
    return RET00, RET01, RET10, RET11

def GCD(a, b):
    print(a.degree(), b.degree())
    q, r = a.quo_rem(b)
    if r == 0:
        return b
    R00, R01, R10, R11 = HGCD(a, b)
    c = R00 * a + R01 * b
    d = R10 * a + R11 * b
    if d == 0:
        return c.monic()
    q, r = c.quo_rem(d)
    if r == 0:
        return d
    return GCD(d, r)

boneh_durfee

Boneh-Durfee适用于低指数加密的情况, 特别适用于低指数加密的情况, 攻击利用规约算法, 将rsa密钥方程转换为求解二维格上的最小近似问题.

平滑数

很基本的一个概念，存在一个数X可以被分解为多个不大于B的素数, 则这个素数被称为平滑数, 其中若X分解

glacierctf2024

Rivest_Shamir_Adleman_Germain

题目

很基础的计算题, 不知道为什么三期竟然没有密码手秒一下, 等报告的过程中顺便写了一下:

#!/usr/bin/env sagemath
# -*- coding: utf-8 -*-
# Respect the shebang and mark file as executable

import os

from Crypto.Util.number import getPrime
from Crypto.Util.number import isPrime
from Crypto.Util.number import bytes_to_long

def generate_primes():
    while True:
        p = getPrime(512),
        q = (2*p) + 1
        r = (2*q) + 1
        s = (2*r) + 1

        if isPrime(q) and isPrime(r) and isPrime(s):
            break
    
    return (p, q, r, s)


def main() -> int:
    (p, q, r, s) = generate_primes()
    N = p * q * r * s
    e = 0x10001

    with open("flag.txt", "r") as flag_file:
        flag = flag_file.read().strip()

    CT = pow(bytes_to_long(flag.encode()), e, N)

    print(f"{N = }")
    print(f"{CT = }")


    return 0

if __name__ == '__main__':
    raise SystemExit(main())

# vim:filetype=python

N = 489654925303072532553659432557377999607856370197579144782976005904927235244321459117898721690940319487769632950077647476152880207627385231603017537961906244964117707813500615680799967895028255666319186794462243666159201392490299439947399915406223652423977002396844720487588735149486903743362109592536081726574342051928022071576485169655694281378301551060632699138055044915993078059902577590451519251321215765308977494770310317350866241246677761542212605478044672014913289740381478940929584556588858045439572693806615268502627912952686133840081188641597461343817750411035667135310831687533531094008308185320371643348451
CT = 58535947031303233853656030097871859886777764034955095086618901763996192727846608049414977429851683454541344096765319691912454768331685486037922533236779909508856486986528041125267338846421238077083738092020495236946742989769815669001100361743526446503248639704900983287986142636083524250650662602975802778548032518674346903013262799229594298599457623347987250272218522320743415393958131916181915804368140008312975210397791293701839101635851486434802271100141743496402698229558250485987421664294229816166263965806962242894230766553316312608696594536239328785792283453559549564751529321240567418095487324718881437825650

解析

题目很清楚有如下关系:

\[\begin{matrix} N = p*q*r*s \\ q = (2*p) + 1 \\ r = (2*q) + 1 \\ s = (2*r) + 1 \end{matrix}\]

因为不喜欢读题结果又考虑复杂了, 既然给出了p,q,r,s几个素数的关系, 可以考虑设未知数去求小根, 结果没解出来, 疑惑了好久又重新一点点审计代码, 发现竟然没有取模, 所以本质只是个简单列方程求未知数, 可以参考sage文档构造EXP.

EXP

使用了EXP库, 或者直接调用sagemath和Crypto库也可以.

from EXP import *

N = 489654925303072532553659432557377999607856370197579144782976005904927235244321459117898721690940319487769632950077647476152880207627385231603017537961906244964117707813500615680799967895028255666319186794462243666159201392490299439947399915406223652423977002396844720487588735149486903743362109592536081726574342051928022071576485169655694281378301551060632699138055044915993078059902577590451519251321215765308977494770310317350866241246677761542212605478044672014913289740381478940929584556588858045439572693806615268502627912952686133840081188641597461343817750411035667135310831687533531094008308185320371643348451
CT = 58535947031303233853656030097871859886777764034955095086618901763996192727846608049414977429851683454541344096765319691912454768331685486037922533236779909508856486986528041125267338846421238077083738092020495236946742989769815669001100361743526446503248639704900983287986142636083524250650662602975802778548032518674346903013262799229594298599457623347987250272218522320743415393958131916181915804368140008312975210397791293701839101635851486434802271100141743496402698229558250485987421664294229816166263965806962242894230766553316312608696594536239328785792283453559549564751529321240567418095487324718881437825650
e = 0x10001

p = var('p')
q = (2*p) + 1
r = (2*q) + 1
s = (2*r) + 1
func_N = p*q*r*s - N
#print(solve(func_N, p))
p = 9352496155192295944243473644483853835662636576410969996619180877861158926367873785037099054018741236476166923118647057249968914650337399039210616026612969
q = (2*p) + 1
r = (2*q) + 1
s = (2*r) + 1
phin = (p-1)*(q-1)*(r-1)*(s-1)
d = pow(e,-1,phin)
print(l2b(pow(CT, d, N)))

sictfround3

gggcccddd

题目

from Crypto.Util.number import *
from enc import flag

m = bytes_to_long(flag)

p = getPrime(512)
q = getPrime(512)
n = p*q
e = 65537
c1 = pow(m,e,n)
c2 = pow(233*m+9527,e,n)
print(f'n = {n}')
print(f'c1 = {c1}')
print(f'c2 = {c2}')
print(f'e = {e}')
"""
n = 71451784354488078832557440841067139887532820867160946146462765529262021756492415597759437645000198746438846066445835108438656317936511838198860210224738728502558420706947533544863428802654736970469313030584334133519644746498781461927762736769115933249195917207059297145965502955615599481575507738939188415191
c1 = 60237305053182363686066000860755970543119549460585763366760183023969060529797821398451174145816154329258405143693872729068255155086734217883658806494371105889752598709446068159151166250635558774937924668506271624373871952982906459509904548833567117402267826477728367928385137857800256270428537882088110496684
c2 = 20563562448902136824882636468952895180253983449339226954738399163341332272571882209784996486250189912121870946577915881638415484043534161071782387358993712918678787398065688999810734189213904693514519594955522460151769479515323049821940285408228055771349670919587560952548876796252634104926367078177733076253
e = 65537
"""

分析

最开始认识franklin板子的题目, 当时只是理解了相关信息攻击, 正式学习HGCD还是又花了一段时间. 题目很标准, 不过e相对来说有点太大了, 如果只是用flanklin的板子许需要跑很久, 因此需要套用HGCD降低复杂度.

EXP

from sage.all import *
from Crypto.Util.number import *
import sys

def HGCD(a, b):
    if 2 * b.degree() <= a.degree() or a.degree() == 1:
        return 1, 0, 0, 1
    m = a.degree() // 2
    a_top, a_bot = a.quo_rem(x**m)
    b_top, b_bot = b.quo_rem(x**m)
    R00, R01, R10, R11 = HGCD(a_top, b_top)
    c = R00 * a + R01 * b
    d = R10 * a + R11 * b
    q, e = c.quo_rem(d)
    d_top, d_bot = d.quo_rem(x**(m // 2))
    e_top, e_bot = e.quo_rem(x**(m // 2))
    S00, S01, S10, S11 = HGCD(d_top, e_top)
    RET00 = S01 * R00 + (S00 - q * S01) * R10
    RET01 = S01 * R01 + (S00 - q * S01) * R11
    RET10 = S11 * R00 + (S10 - q * S11) * R10
    RET11 = S11 * R01 + (S10 - q * S11) * R11
    return RET00, RET01, RET10, RET11

def GCD(a, b):
    q, r = a.quo_rem(b)
    if r == 0:
        return b
    R00, R01, R10, R11 = HGCD(a, b)
    c = R00 * a + R01 * b
    d = R10 * a + R11 * b
    if d == 0:
        return c.monic()
    q, r = c.quo_rem(d)
    if r == 0:
        return d
    return GCD(d, r)

sys.setrecursionlimit(500000)

n = 71451784354488078832557440841067139887532820867160946146462765529262021756492415597759437645000198746438846066445835108438656317936511838198860210224738728502558420706947533544863428802654736970469313030584334133519644746498781461927762736769115933249195917207059297145965502955615599481575507738939188415191
c1 = 60237305053182363686066000860755970543119549460585763366760183023969060529797821398451174145816154329258405143693872729068255155086734217883658806494371105889752598709446068159151166250635558774937924668506271624373871952982906459509904548833567117402267826477728367928385137857800256270428537882088110496684
c2 = 20563562448902136824882636468952895180253983449339226954738399163341332272571882209784996486250189912121870946577915881638415484043534161071782387358993712918678787398065688999810734189213904693514519594955522460151769479515323049821940285408228055771349670919587560952548876796252634104926367078177733076253
e = 65537
R = PolynomialRing(Zmod(n), 'x')
x = R.gen()

f = x**e - c1
g = (233*x+9527)**e - c2

res = GCD(f,g)

m = -res.monic().coefficients()[0]
flag = long_to_bytes(int(m))
print(flag)
# SICTF{45115fb2-84d6-4369-88c2-c8c3d72b4c55}

secconctf

reiwa_rot13

题目

挺开心的一个题, 在贵大和密码师傅们现场写了一下, 结果少条件了没出, 当场社死()

from Crypto.Util.number import *
import codecs
import string
import random
import hashlib
from Crypto.Cipher import AES
from Crypto.Random import get_random_bytes
from flag import flag

p = getStrongPrime(512)
q = getStrongPrime(512)
n = p*q
e = 137

key = ''.join(random.sample(string.ascii_lowercase, 10))
rot13_key = codecs.encode(key, 'rot13')

key = key.encode()
rot13_key = rot13_key.encode()

print("n =", n)
print("e =", e)
print("c1 =", pow(bytes_to_long(key), e, n))
print("c2 =", pow(bytes_to_long(rot13_key), e, n))

key = hashlib.sha256(key).digest()
cipher = AES.new(key, AES.MODE_ECB)
print("encyprted_flag = ", cipher.encrypt(flag))

解析

很基本的类型, 一眼相关信息攻击魔改, 不过在构造线性关系中采用了rot13, 其实原题很简单, 因为key被限制为10位字母: ''.join(random.sample(string.ascii_lowercase, 10)), 我们可以直接得知关系式:

\[rot13\_key = key + b\]

其中b为10位中对256倍数(在long_to_bytes中是256进制, 奇妙的知识增加了)加或减13的和, 也就是有2**10种可能. 当时只顾着flanklin秒了, 前面的key没读题, 当成参有数字随机的不定长度情况去做, 最后只找到b是13的倍数, 还以为需要改板子.

因为多项式足够小, 根据原理可知hgcd甚至会拖慢速度, 所以直接构造秒了.

EXP

from Crypto.Util.number import *
from sage.all import *
from itertools import product
from Crypto.Cipher import AES
import hashlib

def compositeModulusGCD(a, b):
    if (b == 0):
        return a.monic()
    return compositeModulusGCD(b, a % b)

def franklinReiter(n, e, c1, c2, b):
    R = Zmod(n)['x']
    x = R.gen()
    f = x**e - c1
    g = (x+b) ** e - c2
    m = int(n-(compositeModulusGCD(f,g)).coefficients()[0])
    return m

n = 105270965659728963158005445847489568338624133794432049687688451306125971661031124713900002127418051522303660944175125387034394970179832138699578691141567745433869339567075081508781037210053642143165403433797282755555668756795483577896703080883972479419729546081868838801222887486792028810888791562604036658927
e = 137
c1 = 16725879353360743225730316963034204726319861040005120594887234855326369831320755783193769090051590949825166249781272646922803585636193915974651774390260491016720214140633640783231543045598365485211028668510203305809438787364463227009966174262553328694926283315238194084123468757122106412580182773221207234679
c2 = 54707765286024193032187360617061494734604811486186903189763791054142827180860557148652470696909890077875431762633703093692649645204708548602818564932535214931099060428833400560189627416590019522535730804324469881327808667775412214400027813470331712844449900828912439270590227229668374597433444897899112329233
encyprted_flag =  b"\xdb'\x0bL\x0f\xca\x16\xf5\x17>\xad\xfc\xe2\x10$(DVsDS~\xd3v\xe2\x86T\xb1{xL\xe53s\x90\x14\xfd\xe7\xdb\xddf\x1fx\xa3\xfc3\xcb\xb5~\x01\x9c\x91w\xa6\x03\x80&\xdb\x19xu\xedh\xe4"

count = 0
for i in product([13, -13], repeat=10):
    b = 0
    for j in range(len(i)):
        b += i[j] * (0x100**j)

    m = franklinReiter(n,e,c1,c2,b)
    key = long_to_bytes(m)
    try:
        print(key.decode())
        key = hashlib.sha256(key).digest()
        cipher = AES.new(key, AES.MODE_ECB)
        flag = cipher.decrypt(encyprted_flag)
        print(flag)
        break
    except:
        count += 1
        print(f'{count}/1024')

'''
......
792/1024
793/1024
794/1024
dnjqygbmor
b'SECCON{Vim_has_a_command_to_do_rot13._g?_is_possible_to_do_so!!}'
'''

楚慧杯

so_large_e

题目

from Crypto.Util.number import *
import random

flag = open("flag").read().strip()
p = getPrime(512)
q = getPrime(512)
n = p*q
e = random.getrandbits(1024)
assert size(e)==1024
phi = (p-1)*(q-1)
assert GCD(e,phi)==1
d = inverse(e,phi)
assert size(d)==269

pub = (n, e)
PublicKey = RSA.construct(pub)
with open('pub.pem', 'wb') as f :
    f.write(PublicKey.exportKey())

c = pow(m,e,n)
print('c =',c)

print(long_to_bytes(pow(c,d,n)))


#c = 6838759631922176040297411386959306230064807618456930982742841698524622016849807235726065272136043603027166249075560058232683230155346614429566511309977857815138004298815137913729662337535371277019856193898546849896085411001528569293727010020290576888205244471943227253000727727343731590226737192613447347860

解析

已知n, e, 发现存在$\frac{d}{n}=0.26269$, 故猜测为boneh durfee攻击, 修改example()函数的delta和m, 其中$delta=\frac{d}{n}$².

EXP

#sage
from __future__ import print_function
import time

############################################
# Config
##########################################

"""
Setting debug to true will display more informations
about the lattice, the bounds, the vectors...
"""
debug = True

"""
Setting strict to true will stop the algorithm (and
return (-1, -1)) if we don't have a correct
upperbound on the determinant. Note that this
doesn't necesseraly mean that no solutions
will be found since the theoretical upperbound is
usualy far away from actual results. That is why
you should probably use `strict = False`
"""
strict = False

"""
This is experimental, but has provided remarkable results
so far. It tries to reduce the lattice as much as it can
while keeping its efficiency. I see no reason not to use
this option, but if things don't work, you should try
disabling it
"""
helpful_only = True
dimension_min = 7 # stop removing if lattice reaches that dimension

############################################
# Functions
##########################################

# display stats on helpful vectors
def helpful_vectors(BB, modulus):
    nothelpful = 0
    for ii in range(BB.dimensions()[0]):
        if BB[ii,ii] >= modulus:
            nothelpful += 1

    print(nothelpful, "/", BB.dimensions()[0], " vectors are not helpful")

# display matrix picture with 0 and X
def matrix_overview(BB, bound):
    for ii in range(BB.dimensions()[0]):
        a = ('%02d ' % ii)
        for jj in range(BB.dimensions()[1]):
            a += '0' if BB[ii,jj] == 0 else 'X'
            if BB.dimensions()[0] < 60:
                a += ' '
        if BB[ii, ii] >= bound:
            a += '~'
        print(a)

# tries to remove unhelpful vectors
# we start at current = n-1 (last vector)
def remove_unhelpful(BB, monomials, bound, current):
    # end of our recursive function
    if current == -1 or BB.dimensions()[0] <= dimension_min:
        return BB

    # we start by checking from the end
    for ii in range(current, -1, -1):
        # if it is unhelpful:
        if BB[ii, ii] >= bound:
            affected_vectors = 0
            affected_vector_index = 0
            # let's check if it affects other vectors
            for jj in range(ii + 1, BB.dimensions()[0]):
                # if another vector is affected:
                # we increase the count
                if BB[jj, ii] != 0:
                    affected_vectors += 1
                    affected_vector_index = jj

            # level:0
            # if no other vectors end up affected
            # we remove it
            if affected_vectors == 0:
                print("* removing unhelpful vector", ii)
                BB = BB.delete_columns([ii])
                BB = BB.delete_rows([ii])
                monomials.pop(ii)
                BB = remove_unhelpful(BB, monomials, bound, ii-1)
                return BB

            # level:1
            # if just one was affected we check
            # if it is affecting someone else
            elif affected_vectors == 1:
                affected_deeper = True
                for kk in range(affected_vector_index + 1, BB.dimensions()[0]):
                    # if it is affecting even one vector
                    # we give up on this one
                    if BB[kk, affected_vector_index] != 0:
                        affected_deeper = False
                # remove both it if no other vector was affected and
                # this helpful vector is not helpful enough
                # compared to our unhelpful one
                if affected_deeper and abs(bound - BB[affected_vector_index, affected_vector_index]) < abs(bound - BB[ii, ii]):
                    print("* removing unhelpful vectors", ii, "and", affected_vector_index)
                    BB = BB.delete_columns([affected_vector_index, ii])
                    BB = BB.delete_rows([affected_vector_index, ii])
                    monomials.pop(affected_vector_index)
                    monomials.pop(ii)
                    BB = remove_unhelpful(BB, monomials, bound, ii-1)
                    return BB
    # nothing happened
    return BB

""" 
Returns:
* 0,0   if it fails
* -1,-1 if `strict=true`, and determinant doesn't bound
* x0,y0 the solutions of `pol`
"""
def boneh_durfee(pol, modulus, mm, tt, XX, YY):
    """
    Boneh and Durfee revisited by Herrmann and May
    
    finds a solution if:
    * d < N^delta
    * |x| < e^delta
    * |y| < e^0.5
    whenever delta < 1 - sqrt(2)/2 ~ 0.292
    """

    # substitution (Herrman and May)
    PR.<u, x, y> = PolynomialRing(ZZ)
    Q = PR.quotient(x*y + 1 - u) # u = xy + 1
    polZ = Q(pol).lift()

    UU = XX*YY + 1

    # x-shifts
    gg = []
    for kk in range(mm + 1):
        for ii in range(mm - kk + 1):
            xshift = x^ii * modulus^(mm - kk) * polZ(u, x, y)^kk
            gg.append(xshift)
    gg.sort()

    # x-shifts list of monomials
    monomials = []
    for polynomial in gg:
        for monomial in polynomial.monomials():
            if monomial not in monomials:
                monomials.append(monomial)
    monomials.sort()
    
    # y-shifts (selected by Herrman and May)
    for jj in range(1, tt + 1):
        for kk in range(floor(mm/tt) * jj, mm + 1):
            yshift = y^jj * polZ(u, x, y)^kk * modulus^(mm - kk)
            yshift = Q(yshift).lift()
            gg.append(yshift) # substitution
    
    # y-shifts list of monomials
    for jj in range(1, tt + 1):
        for kk in range(floor(mm/tt) * jj, mm + 1):
            monomials.append(u^kk * y^jj)

    # construct lattice B
    nn = len(monomials)
    BB = Matrix(ZZ, nn)
    for ii in range(nn):
        BB[ii, 0] = gg[ii](0, 0, 0)
        for jj in range(1, ii + 1):
            if monomials[jj] in gg[ii].monomials():
                BB[ii, jj] = gg[ii].monomial_coefficient(monomials[jj]) * monomials[jj](UU,XX,YY)

    # Prototype to reduce the lattice
    if helpful_only:
        # automatically remove
        BB = remove_unhelpful(BB, monomials, modulus^mm, nn-1)
        # reset dimension
        nn = BB.dimensions()[0]
        if nn == 0:
            print("failure")
            return 0,0

    # check if vectors are helpful
    if debug:
        helpful_vectors(BB, modulus^mm)
    
    # check if determinant is correctly bounded
    det = BB.det()
    bound = modulus^(mm*nn)
    if det >= bound:
        print("We do not have det < bound. Solutions might not be found.")
        print("Try with highers m and t.")
        if debug:
            diff = (log(det) - log(bound)) / log(2)
            print("size det(L) - size e^(m*n) = ", floor(diff))
        if strict:
            return -1, -1
    else:
        print("det(L) < e^(m*n) (good! If a solution exists < N^delta, it will be found)")

    # display the lattice basis
    if debug:
        matrix_overview(BB, modulus^mm)

    # LLL
    if debug:
        print("optimizing basis of the lattice via LLL, this can take a long time")

    BB = BB.LLL()

    if debug:
        print("LLL is done!")

    # transform vector i & j -> polynomials 1 & 2
    if debug:
        print("looking for independent vectors in the lattice")
    found_polynomials = False
    
    for pol1_idx in range(nn - 1):
        for pol2_idx in range(pol1_idx + 1, nn):
            # for i and j, create the two polynomials
            PR.<w,z> = PolynomialRing(ZZ)
            pol1 = pol2 = 0
            for jj in range(nn):
                pol1 += monomials[jj](w*z+1,w,z) * BB[pol1_idx, jj] / monomials[jj](UU,XX,YY)
                pol2 += monomials[jj](w*z+1,w,z) * BB[pol2_idx, jj] / monomials[jj](UU,XX,YY)

            # resultant
            PR.<q> = PolynomialRing(ZZ)
            rr = pol1.resultant(pol2)

            # are these good polynomials?
            if rr.is_zero() or rr.monomials() == [1]:
                continue
            else:
                print("found them, using vectors", pol1_idx, "and", pol2_idx)
                found_polynomials = True
                break
        if found_polynomials:
            break

    if not found_polynomials:
        print("no independant vectors could be found. This should very rarely happen...")
        return 0, 0
    
    rr = rr(q, q)

    # solutions
    soly = rr.roots()

    if len(soly) == 0:
        print("Your prediction (delta) is too small")
        return 0, 0

    soly = soly[0][0]
    ss = pol1(q, soly)
    solx = ss.roots()[0][0]

    #
    return solx, soly

def example():
    ############################################
    # How To Use This Script
    ##########################################

    #
    # The problem to solve (edit the following values)
    #

    # the modulus
    N = 116518679305515263290840706715579691213922169271634579327519562902613543582623449606741546472920401997930041388553141909069487589461948798111698856100819163407893673249162209631978914843896272256274862501461321020961958367098759183487116417487922645782638510876609728886007680825340200888068103951956139343723
    e = 113449247876071397911206070019495939088171696712182747502133063172021565345788627261740950665891922659340020397229619329204520999096535909867327960323598168596664323692312516466648588320607291284630435682282630745947689431909998401389566081966753438869725583665294310689820290368901166811028660086977458571233
    # the public exponent
    # the hypothesis on the private exponent (the theoretical maximum is 0.292)
    delta = .27 # this means that d < N^delta

    #
    # Lattice (tweak those values)
    #

    # you should tweak this (after a first run), (e.g. increment it until a solution is found)
    m = 5 # size of the lattice (bigger the better/slower)

    # you need to be a lattice master to tweak these
    t = int((1-2*delta) * m)  # optimization from Herrmann and May
    X = 2*floor(N^delta)  # this _might_ be too much
    Y = floor(N^(1/2))    # correct if p, q are ~ same size

    #
    # Don't touch anything below
    #

    # Problem put in equation
    P.<x,y> = PolynomialRing(ZZ)
    A = int((N+1)/2)
    pol = 1 + x * (A + y)

    #
    # Find the solutions!
    #

    # Checking bounds
    if debug:
        print("=== checking values ===")
        print("* delta:", delta)
        print("* delta < 0.292", delta < 0.292)
        print("* size of e:", int(log(e)/log(2)))
        print("* size of N:", int(log(N)/log(2)))
        print("* m:", m, ", t:", t)

    # boneh_durfee
    if debug:
        print("=== running algorithm ===")
        start_time = time.time()

    solx, soly = boneh_durfee(pol, e, m, t, X, Y)

    # found a solution?
    if solx > 0:
        print("=== solution found ===")
        if False:
            print("x:", solx)
            print("y:", soly)

        d = int(pol(solx, soly) / e)
        print("private key found:", d)
    else:
        print("=== no solution was found ===")

    if debug:
        print(("=== %s seconds ===" % (time.time() - start_time)))

if __name__ == "__main__":
    example()

参考文献

whx1003.多项式gcd的正确姿势:Half-GCD算法[EB/OL]博客园.https://www.cnblogs.com/whx1003/p/16217087.html.2022-05-02. ↩
DexterJie.杂记(1)[EB/OL]个人博客.https://dexterjie.github.io/2023/12/17/%E6%9D%82%E8%AE%B0/?highlight=dasctf.2023-12-17. ↩

分享到

Twitter Facebook LinkedIn

CryingN

[Crypto学习笔记] 简单的RSA类题目

目录

前置概念

rsa原理

gcd

hgcd

相关信息攻击

boneh_durfee

平滑数

glacierctf2024

Rivest_Shamir_Adleman_Germain

题目

解析

EXP

sictfround3

gggcccddd

题目

分析

EXP

secconctf

reiwa_rot13

题目

解析

EXP

楚慧杯

so_large_e

题目

解析

EXP

参考文献

分享到

你可能感兴趣的

[awdp学习笔记] 密码系统类题目

[awdp学习笔记] fix部分

[环境配置] Archwsl安装与配置教程

[Crypto学习笔记] 代数类题目