[Crypto学习笔记] 简单的RSA类题目
发布时间：
有一段时间我在进行反思, 受以前的一些经历限制, 一直以来是跳跃性地学习密码学, 以至于一边在忙着一些复杂的东西, 但又有很多基本概念实际上并没有搞懂, 所以后来有了些想法, 决定比较系统地梳理一下知识点.
目录
前置概念
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在取模运算上做了优化, 想象有项数极高的两个多项式, 在最坏情况下每次辗转相除可以消去一项, 实际上在整除过程中往往只需要在高次项就可以计算出答案, 但是取模需要精度计算到最后, 造成了计算资源浪费. 考虑存在以下两个多项式1:
$\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)
相关信息攻击
相关信息类题型一般涉及franklin-reiter攻击和HalfGCD算法考点, 以下先定义相关信息的题型:
\[\begin{matrix} c_1\equiv m_1^e \mod{n} \\ c_2\equiv m_2^e \mod{n} \\ m_2 = am_1+b \end{matrix}\]考虑到
\[m_2 \equiv f(m_1) \mod{n}\]那么我们可以知道m2是
\(f(x)^e \equiv c_1 \mod{n}\) 的一个解,即它是方程 \(f(x)^e-c_1\) 在模n意义下的一个根.同样,m2是 \(x^e\) 模n意义下的一个根.所以有 \(x-m_2\) 同时整除以上两个多项式, 可以求得两个多项式的最大公因子, 如果最大公因子恰好是线性的话, 那么我们可以求得m2. 在e=3的情况下, 最大公因子一定是线性的.
当e=3,且
\[f(x)=ax+b\]的情况下,经过推导我们可以得到:
上面的式子中右边所有的参数都是已知的,所以可以求得对应的信息.
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)), 我们可以直接得知关系式:
其中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 = 116518679305515263290840706715579691213922169271634579327519562902613543582623449606741546472920401997930041388553141909069487589461948798111698856100819163407893673249162209631978914843896272256274862501461321020961958367098759183487116417487922645782638510876609728886007680825340200888068103951956139343723
#e = 113449247876071397911206070019495939088171696712182747502133063172021565345788627261740950665891922659340020397229619329204520999096535909867327960323598168596664323692312516466648588320607291284630435682282630745947689431909998401389566081966753438869725583665294310689820290368901166811028660086977458571233
解析
已知n, e, 发现存在\(\frac{d}{n}=0.26269\), 故猜测为boneh durfee攻击, 修改example()函数的delta和m, 其中\(delta=\frac{d}{n}\)2.
EXP
from Crypto.Util.number import long_to_bytes
from hashlib import md5
import re
import string
alphabet = string.printable[:71]
p = Integer(len(alphabet))
with open("./output", "r") as p:
data = p.read().split("\n")[:-1]
# print(data)
data = [re.findall(r"\d+", d) for d in data]
data = [[Integer(di) for di in d] for d in data]
# print(data[:11])
E = matrix(GF(71), data[:11])
LUL = matrix(GF(71), data[11:22])
ULUL = matrix(GF(71), data[22:33])
R1LU8 = matrix(GF(71), data[33:])
U = LUL.solve_left(ULUL)
LU8=(LUL*U)**4
R = (LU8.solve_left(R1LU8)).inverse()
AR = U.solve_right(E)
A = AR - R
m = "".join([alphabet[A[5*k // 11, 5*k % 11]] for k in range(24)])
print(md5(m.encode()).hexdigest())
# 3529d01631d8436edca1c78ad82b6f26
broncoctf2025
rahhh-sa
模在负数上的rsa.
题目
# RAHHH!!!!!
import math
e = 65537
p = -811
q = ??????
n = p * q
phi_n = (p + 1) * (q + 1)
# but first, a word from
# our sponsored function!
def extendedEuclideanAlgo(e, phi_n):
A1, A2, A3 = 1, 0, phi_n # var "b"
B1, B2, B3 = 0, 1, e # var "a
while (True):
if B3 == 0:
return -1
# indicates no inverse!
if B3 == 1:
return B2
# B2: modular inverse
Q = math.floor(A3 / B3)
T1, T2, T3 = A1 - (Q * B1), A2 - (Q * B2), A3 - (Q * B3)
A1, A2, A3 = B1, B2, B3
B1, B2, B3 = T1, T2, T3
def encrypt(int, e, n):
return pow(int, e, -n)
e = 65537
n = 3429719
c = [-53102, -3390264, -2864697, -3111409, -2002688, -2864697, -1695722, -1957072, -1821648, -1268305, -3362005, -712024, -1957072, -1821648, -1268305, -732380, -2002688, -967579, -271768, -3390264, -712024, -1821648, -3069724, -732380, -892709, -271768, -732380, -2062187, -271768, -292609, -1599740, -732380, -1268305, -712024, -271768, -1957072, -1821648, -3418677, -732380, -2002688, -1821648, -3069724, -271768, -3390264, -1847282, -2267004, -3362005, -1764589, -293906, -1607693]
p = -811
分析
刚看到生成密文c是拆字符循环生成, 直接就暴力破解了, 主要是extendedEuclideanAlgo(e, phi_n)扩展欧几里得给脑子干烧了, 可以直接暴力破解:
# RAHHH!!!!!
import math
e = 65537
p = -811
e = 65537
n = 3429719
c = [-53102, -3390264, -2864697, -3111409, -2002688, -2864697, -1695722, -1957072, -1821648, -1268305, -3362005, -712024, -1957072, -1821648, -1268305, -732380, -2002688, -967579, -271768, -3390264, -712024, -1821648, -3069724, -732380, -892709, -271768, -732380, -2062187, -271768, -292609, -1599740, -732380, -1268305, -712024, -271768, -1957072, -1821648, -3418677, -732380, -2002688, -1821648, -3069724, -271768, -3390264, -1847282, -2267004, -3362005, -1764589, -293906, -1607693]
q = n // p
phi_n = (p + 1) * (q + 1)
def encrypt(int, e, n):
return pow(int, e, -n)
flag = 'bronco{'
for i in c[7:-1]:
for j in range(150):
if i == encrypt(j, e, n):
flag += chr(j)
break
flag += '}'
print(flag)
print(len(flag) == len(c))
# bronco{m4th3m4t1c5_r34l1y_1s_qu1t3_m4g1c4l_raAhH!}
# True
被烟雾弹干扰了, 实际上与rsa最大的区别是取了负模, 只需要取绝对值或者将rsa的思路放在负数域就能拿到flag
EXP
直接在负数域计算
e = 65537
n = 3429719
c = [-53102, -3390264, -2864697, -3111409, -2002688, -2864697, -1695722, -1957072, -1821648, -1268305, -3362005, -712024, -1957072, -1821648, -1268305, -732380, -2002688, -967579, -271768, -3390264, -712024, -1821648, -3069724, -732380, -892709, -271768, -732380, -2062187, -271768, -292609, -1599740, -732380, -1268305, -712024, -271768, -1957072, -1821648, -3418677, -732380, -2002688, -1821648, -3069724, -271768, -3390264, -1847282, -2267004, -3362005, -1764589, -293906, -1607693]
p = -811
phin = (p+1)*(q+1)
d = pow(e, -1, phin)
flag = ''
for i in c:
flag += chr(pow(i, d, n))
print(flag)
# bronco{m4th3m4t1c5_r34l1y_1s_qu1t3_m4g1c4l_raAhH!}
恢复到普通rsa计算
e = 65537
n = 3429719
c = [-53102, -3390264, -2864697, -3111409, -2002688, -2864697, -1695722, -1957072, -1821648, -1268305, -3362005, -712024, -1957072, -1821648, -1268305, -732380, -2002688, -967579, -271768, -3390264, -712024, -1821648, -3069724, -732380, -892709, -271768, -732380, -2062187, -271768, -292609, -1599740, -732380, -1268305, -712024, -271768, -1957072, -1821648, -3418677, -732380, -2002688, -1821648, -3069724, -271768, -3390264, -1847282, -2267004, -3362005, -1764589, -293906, -1607693]
p = -811
p = abs(p)
q = n // p
phin= (p-1)*(q-1)
d = pow(e, -1, phin)
flag = ''
for i in c:
flag += chr(n - pow(abs(i), d, n))
print(flag)
# bronco{m4th3m4t1c5_r34l1y_1s_qu1t3_m4g1c4l_raAhH!}
参考文献
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. ↩
