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

6 分钟阅读时长

发布时间： 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)

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!!}'
'''

参考文献

whx1003.多项式gcd的正确姿势:Half-GCD算法[EB/OL]博客园.https://www.cnblogs.com/whx1003/p/16217087.html.2022-05-02. ↩

分享到

Twitter Facebook LinkedIn

CryingN

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

目录

前置概念

rsa原理

gcd

hgcd

相关信息攻击

glacierctf2024

Rivest_Shamir_Adleman_Germain

题目

解析

EXP

sictfround3

gggcccddd

题目

分析

EXP

secconctf

reiwa_rot13

题目

解析

EXP

参考文献

分享到

你可能感兴趣的

[Crypto学习笔记] Edwards curve类题目

[Crypto学习笔记] Schmidt-Samona密码系统

[Crypto学习笔记] DES对称加密类题目

[Crypto学习笔记] Hash类型攻击题目