虎符CTF2022

​ 和0x401的师傅们参加了虎符，进入了决赛，被带飞的感觉真好2333。本篇将持续记录对赛题的复现。

RRSSAA

题目：

from random import randint
from secret import hint, flag

def seq(r, k):
    v = [r, 2]
    for i in range(1, k):
        v = [r*v[0]-v[1], v[0]]
    ret = v[0] if k != 0 else v[1]
    return ret

def encrypt(m, e, n):
    while True:
        r = randint(1, n - 1)
        if r != 2 and r != n - 2 and GCD(r, n) == 1:
            break
    v = seq(r, e)
    print(r)
    return ((1 + m*n) * v) % n**2

def go(beta, msg):
    nbits = 1024
    delta = 0.63

    p = getPrime(nbits // 2)
    q = next_prime(p + (1 << int(nbits * beta)))
    n = p * q
    phi = (p**2 - 1) * (q**2 - 1)

    while True:
        d = getPrime(int(nbits * delta))
        if GCD(d, phi) == 1:
            e = inverse(d, phi)
            if GCD(e, phi) == 1:
                break

    m = bytes_to_long(msg)
    c = int(encrypt(m, e, n))

    print(f"n = {n}")
    print(f"e = {e}")
    print(f"c = {c}")

go(0.33, hint)
go(0.44, flag)

'''
n = 122774778628333786198247673730199699244621671207929503475974934116435291656353398717362903500544713183492877018211738292001516168567879903073296829793548881467270228989482723510323780292947403861546283099122868428902480999485625751961457245487615479377459707992802193391975415447673215862245349068018710525679
e = 7105408692393780974425936359246908629062633111464343215149184058052422839553782885999575538955213539904607968494147112651103116202742324255190616790664935322773999797774246994193641076154786429287567308416036562198486649223818741008968261111017589015617705905631979526370180766874051731174064076871339400470062519500450745667838729104568633808272577378699913068193645578675484681151593983853443489561431176000585296710615726640355782811266099023653898050647891425956485791437516020367967793814415345332943552405865306305448753989707540163585481006631816856260061985275944250758886027672221219132999488907097750048011
c = 2593129589804979134490367446026701647048897831627696427897506570257238733858989741279626614121210703780002736667183915826429635213867589464112850355422817678245007337553349507744893376944140333333044928907283949731124795240808354521353751152149301719465724014407412256933045835977081658410026081895650068864922666975525001601181989114436054060461228877148361720945120260382962899756912493868467226822547185396096960560068874538680230073168773182775945272726468512949751672553541335307512429217493003429882831235199830121519272447634533018024087697385363918421438799206577619692685090186486444886371979602617584956259
n = 59969098213446598961510550233718258878862148298191323654672950330070587404726715299685997489142290693126366408044603303463518341243526241117556011994804902686998166238333549719269703453450958140262475942580009981324936992976252832887660977703209225426388975233018602730303262439218292062822981478737257836581
e = 970698965238639683403205181589498135440069660016843488485401994654202837058754446853559143754852628922125327583411039117445415303888796067576548626904070971514824878024057391507617988385537930417136322298476467215300995795105008488692961624917433064070351961856959734368784774555385603000155569897078026670993484466622344106374637350023474339105113172687604783395923403613555236693496567851779400707953027457705617050061193750124237055690801725151098972239120476113241310088089420901051617493693842562637896252448161948655455277146925913049354086353328749354876619287042077221173795354616472050669799421983520421287
c = 2757297249371055260112176788534868300821961060153993508569437878576838431569949051806118959108641317578931985550844206475198216543139472405873345269094341570473142756599117266569746703013099627523306340748466413993624965897996985230542275127290795414763432332819334757831671028121489964563214463689614865416498886490980692515184662350519034273510244222407505570929178897273048405431658365659592815446583970229985655015539079874797518564867199632672678818617933927005198847206019475149998468493858071672920824599672525667187482558622701227716212254925837398813278836428805193481064316937182435285668656233017810444672
'''

解题思路

​ part 1：

​ p，q的生成过程有缺陷，具体为p和q大约相差1 << int(nbits beta)，那么可以爆破差值附近bit的值，来获得准确的q-p，利用（q-p）^ 2 + 4pq开方来获得p+q（iroot有解的时候说明q-p正确）。拿到p+q以后可以联立pq = n解出p，q，我使用的z3。

# 分解p、q的代码（非预期）
import gmpy2
from z3 import *

nbits = 1024
beta = 0.44
num = 1 << int(nbits * beta)

n = 59969098213446598961510550233718258878862148298191323654672950330070587404726715299685997489142290693126366408044603303463518341243526241117556011994804902686998166238333549719269703453450958140262475942580009981324936992976252832887660977703209225426388975233018602730303262439218292062822981478737257836581

for i in range(-2**20,2**20):
    num1 = num+i
    x = num1**2 + 4*n
    if gmpy2.iroot(x, 2)[1]:
        print(gmpy2.iroot(x, 2))
        break

sum_ = 15487943467542306207164957522779915558232722677017868704346602824547506038541073770618393546150569709175993688022768031705225684075989372415124252944311482
p = Int("p")
q = Int('q')
solve(p*q == n,p+q == sum_ )

​ part2：

​ 实际上是基于lucas序列的公钥密码体制LUC，原理详见“一种新的基于 Lucas 序列的公钥密码体制”这篇论文。最关键的部分是要理解lucas序列的元素递推组成一个群，其满足逆元的性质，比如递推e次得到的元素和递推d次得到的元素一样，将d记作e的逆元。de是在phi上互为逆元，phi的求法需利用勒让德符号，详见论文。

​ 所以part2的关键在于求出r，再将r带入lucas递推公式求出v。

​ 可利用的关系为：

$$v \equiv c mod n$$ $$r \equiv seq(v,d)(modn)$$

​ 注意：1、d为e模phi的逆2、由于v和c同余n所以seq（v,d）也要建立在模n上计算3、r小于n所以modn^2和modn结果是一致的4、最后求出r以后再将r，e带入lucas序列函数seq中求出v。在带入seq计算的时候，为了迅速计算，需要用矩阵快速幂优化。但由于sage的矩阵乘法已经优化为快速幂了，所以不需要自己实现。找矩阵系数的方法可以这样：

​ 同时，sage也有lucas序列函数，sage.rings.finite_rings.integer_mod import lucas

​ part3：类同态解密

​

$$uv\equiv1modn^{2}$$ $$(cu-1)//n\equiv m(mod)n^{2}$$

from Crypto.Util.number import inverse, long_to_bytes
from sage.all import *

p = 7743971733771153102128801312798743998017713722732925283466018690899116898707556486947918196848489007935614742583856884731087798825462330340492923214926391
q = 7743971733771153105036156209981171560215008954284943420880584133648389139833517283670475349302080701240378945438911146974137885250527042074631329729385091
n = p * q
MOD = n * n
phi = (p**2 - 1) * (q**2 - 1)


def seq(r, k):
    A = matrix(Zmod(MOD), [[r, -1], [1, 0]])
    x = matrix(Zmod(MOD), [[2], [r]])
    return int((A**k * x)[0, 0])


def L(x):
    return (x % MOD - 1) // n

e = 970698965238639683403205181589498135440069660016843488485401994654202837058754446853559143754852628922125327583411039117445415303888796067576548626904070971514824878024057391507617988385537930417136322298476467215300995795105008488692961624917433064070351961856959734368784774555385603000155569897078026670993484466622344106374637350023474339105113172687604783395923403613555236693496567851779400707953027457705617050061193750124237055690801725151098972239120476113241310088089420901051617493693842562637896252448161948655455277146925913049354086353328749354876619287042077221173795354616472050669799421983520421287
c = 2757297249371055260112176788534868300821961060153993508569437878576838431569949051806118959108641317578931985550844206475198216543139472405873345269094341570473142756599117266569746703013099627523306340748466413993624965897996985230542275127290795414763432332819334757831671028121489964563214463689614865416498886490980692515184662350519034273510244222407505570929178897273048405431658365659592815446583970229985655015539079874797518564867199632672678818617933927005198847206019475149998468493858071672920824599672525667187482558622701227716212254925837398813278836428805193481064316937182435285668656233017810444672

d = inverse(e, phi)
r = seq(c, d) % n
v = seq(r, e)
print(long_to_bytes(L(c * inverse(v, MOD))))
#HFCTF{5eb34942-bd0d-4efd-b0e1-a73225d92678}