20200219-VNCTF-CryptoSecWriteUp

Posted on Edited on In , Views: Symbols count in article: 20k Reading time ≈ 18 mins.

 

CRT

题目描述

Do you know the Chinese Remainder Theorem sometimes may not only have one solution?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import hashlib
from functools import reduce
from Crypto.Util.number import *

ms = [getRandomNBitInteger(128) for i in range(8)]
p = reduce(lambda x, y: x*y, ms)
x = getRandomRange(1, p)
cs = [x % m for m in ms]

flag = "flag{" + hashlib.sha256(str(x).encode()).hexdigest() + "}"
assert("4b93deeb" in flag)

# ms = [284461942441737992421992210219060544764, 218436209063777179204189567410606431578, 288673438109933649911276214358963643204, 239232622368515797881077917549177081575, 206264514127207567149705234795160750411, 338915547568169045185589241329271490503, 246545359356590592172327146579550739141, 219686182542160835171493232381209438048]
# cs = [273520784183505348818648859874365852523, 128223029008039086716133583343107528289, 5111091025406771271167772696866083419, 33462335595116820423587878784664448439, 145377705960376589843356778052388633917, 128158421725856807614557926615949143594, 230664008267846531848877293149791626711, 94549019966480959688919233343793910003]

解题思路

题目很简单，但是自己饶了好多弯

首先，一看，这不就是构造了8个同余式吗，直接CRT结果不对

原来模数不互素，于是我在sage中分解了这8个数

image-20210705194105634

然后在保证模数尽可能大的原则下，写完了脚本。但结果依旧不对，并且出来的x是1006位，由题目可知x是属于$[1, 2^{1024}]$的，所以显然x是落在了$[2^{1007},2^{1024}]$这段区间。总之模数不够

不过，这也不是最困扰我的地方，与题目提示不同，我第一个想到的是，扩大模数，构造如下的同余方程
$$
\begin{cases}
x\equiv cs_1\ (mod\ ms_1)\\
x\equiv cs_2\ (mod\ ms_2)\\
\vdots\qquad \vdots \qquad\qquad \vdots\\
x\equiv cs_8\ (mod\ ms_8)\\
x\equiv cs_9\ (mod\ ms_9)
\end{cases}\notag
$$
其中ms9是一个随机20位的素数，因为1007+20差不多就可以达到1024的大小

编写脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import hashlib
from Crypto.Util.number import *
import copy

ms = [284461942441737992421992210219060544764, 218436209063777179204189567410606431578, 288673438109933649911276214358963643204, 239232622368515797881077917549177081575, 206264514127207567149705234795160750411, 338915547568169045185589241329271490503, 246545359356590592172327146579550739141, 219686182542160835171493232381209438048]
cs = [273520784183505348818648859874365852523, 128223029008039086716133583343107528289, 5111091025406771271167772696866083419, 33462335595116820423587878784664448439, 145377705960376589843356778052388633917, 128158421725856807614557926615949143594, 230664008267846531848877293149791626711, 94549019966480959688919233343793910003]

new_ms = copy.deepcopy(ms)
my_ms = getPrime(20)
new_ms.append(my_ms)

for i in range(my_ms):
    new_cs = copy.deepcopy(cs)
    new_cs.append(i)
    x = crt(new_cs, new_ms)
    flag = "flag{" + hashlib.sha256(str(x).encode()).hexdigest() + "}"
    if '4b93deeb' in flag:
        print(flag)
        break

再在该文件位置打开cmd，进入子系统，打开sage，输入

1
load("脚本文件名")

image-20210705200158602

就直接出来了

注意下浅拷贝的问题

其他师傅的思路

虽然这样做也无可厚非，但是还是没有能精确get到出题人的意思

最直接的思路应该是，CRT解出来的其实蕴含了一系列的解，其通式可以写成
$$
{kM+\sum_{i=1}^na_it_iM_i;\ k\in\mathbb{Z} }\notag
$$
所以只要用CRT解出来x，然后爆破k就好，因为确实比较接近，上下两种方法的复杂度是同一级别的

当然上述通式的M是不互素的模数的积，贴一下脚本，不愧是尚师傅

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import hashlib
from Crypto.Util.number import *
from functools import reduce

ms = [284461942441737992421992210219060544764, 218436209063777179204189567410606431578, 288673438109933649911276214358963643204, 239232622368515797881077917549177081575, 206264514127207567149705234795160750411, 338915547568169045185589241329271490503, 246545359356590592172327146579550739141, 219686182542160835171493232381209438048]
cs = [273520784183505348818648859874365852523, 128223029008039086716133583343107528289, 5111091025406771271167772696866083419, 33462335595116820423587878784664448439, 145377705960376589843356778052388633917, 128158421725856807614557926615949143594, 230664008267846531848877293149791626711, 94549019966480959688919233343793910003]
p = reduce(lambda xx, yy: lcm(xx, yy), ms)

x = crt(cs, ms)
k = 0
while True:
    xx = k*p + x
    k += 1
    flag = "flag{" + hashlib.sha256(str(xx).encode()).hexdigest() + "}"
    if "4b93deeb" in flag:
        print(flag)
        break

Fast

题目描述

This is a modified RSA scheme that once proposed at a cryptography conference to achieve faster decryption. But, there seems something wrong with it.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
from Crypto.Util.number import *
from secret import flag


p = getPrime(1024)
q = getPrime(1024)
N = p * q

g, r1, r2 = [getRandomRange(1, N) for _ in range(3)]
g1 = pow(g, r1 * (p-1), N)
g2 = pow(g, r2 * (q-1), N)


def encrypt(m):
    s1, s2 = [getRandomRange(1, N) for _ in range(2)]
    c1 = (m * pow(g1, s1, N)) % N
    c2 = (m * pow(g2, s2, N)) % N
    return (c1, c2)

def decrypt(c1, c2):
    xp = c1 % p
    xq = c2 % q
    # Chinese Remainder Theorem
    m = (xp*inverse(q, p)*q + xq*inverse(p, q)*p) % N
    return m


c = encrypt(bytes_to_long(flag))


# N = 18680643069610062851842282268594530254220611012409807422663284548187050713427682950720783343430650669361838067625768840896513125210105582070603021732086193955893838077699465426052925750736212977005683541174195320832791835197114668838654054444342903298662698415765898335350206380896849522280206304272801325820946987172164086644949521111058774180676742851681476123338557138770304164634321305204827406522957769478330124484710532963132900017800651579612646041955628867746525508376194147796920773364680264059390497210260540079810501777507814448518995581208169818764701641258963569599247156932381367802991222265241699715283
# g1 = 9143176283300810019842153344177123108612540016879643936458724056602746667157014763960725115919119704406826965726023263657276550779443988565368344040505696950820899770544814163379169539926317676679421275092688200844094929042154854719312788471536324082041360841253720783220459009201882865091829118575721525038404689868986360373373122049951274015083845966946475469982961355934516388706446794517870569063777231434618411404965077775991870069073539415961610645268985004687402050059891500490949250730689691141954694508001895390336750734542724392709744200091587065816283592253967715080611459937165344139809223328071517060208
# g2 = 14068322834597276347776814624877614869834816383564391664570268934537693322688875343215293618493363798985047779057952636529313879548457643220996398640913517182122425631198219387988691569709691279442005545716133131472147592456812502863851227108284027033557263611949365667779259585770738623603814004666845554284808166195201470503432803440754207350347128045893594280079379926676477680556845095378093693409219131090910168117334308781843178748431526974047817218228075136005979538773141427004682344298827618677773735288946271346252828348742296301538573408254015281232250841148556304927266143397565889649305095857756884049430
# c1, c2 = (3976514029543484086411168675941075541422870678409709261442618832911574665848843566949154289825219682094719766762966082440586568781997199077781276145091509192208487682443007457513002005089654365915817414921574344557570444253187757317116858499013550050579856269915915792827620535138057468531410166908365364129001407147467636145589396570815405571923148902993581000542566387654639930651683044853608873583911638108204074537952317056718986683846742909366072461130053275195290631718363272923316002049685111871888148244026652658482359335651889139243735138819453744763293112267738369048641158946411500606588429007794613880534, 18524535479582837341745231233387403662294605513261199630593257391163433751052467785080620993007681605662927226603747560698627838567782891522546977611597418150309028806158429831471152782211111046118637630899456903846057977815397285171313888516791822545633820066408276065732715348834255021260666966934592884548856831383262013360819013814149529393178712576141627031723067564594282618223686778534522328204603249125537258294561872667849498796757523663858312311082034700705599706428944071848443463999351872482644584735305157234751806369172212650596041534643187402820399145288902719434158798638116870325144146218568810928344)

解题思路

n可以被分解，解密函数也是现成的，而且是正确的

应该是出题人有意为之吧

编写脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from Crypto.Util.number import *


def decrypt(c1, c2):
    xp = c1 % p
    xq = c2 % q
    # Chinese Remainder Theorem
    m = (xp*inverse(q, p)*q + xq*inverse(p, q)*p) % N
    return m


N = 18680643069610062851842282268594530254220611012409807422663284548187050713427682950720783343430650669361838067625768840896513125210105582070603021732086193955893838077699465426052925750736212977005683541174195320832791835197114668838654054444342903298662698415765898335350206380896849522280206304272801325820946987172164086644949521111058774180676742851681476123338557138770304164634321305204827406522957769478330124484710532963132900017800651579612646041955628867746525508376194147796920773364680264059390497210260540079810501777507814448518995581208169818764701641258963569599247156932381367802991222265241699715283
p = 106417460801952098564106499070151038873024911455536068339939244771790540941720274028587207976808157868694798197258813111268537142798255715538795631061310640662123200632946626357221258957037900275496387833531601196435353735799649271157394995634449593246448856875377066127076028119584523015225013672972959211463
q = 175541146432497750706994831036579922743699110188170130349078711914372625934257198871368005366941949929286673808928975466227805723983786985788458460399280363091838402146937391317438052439989533790389951909401937742849194965413829547962616241584178560041639076246949503118700746929605640733813016659832730773141
g1 = 9143176283300810019842153344177123108612540016879643936458724056602746667157014763960725115919119704406826965726023263657276550779443988565368344040505696950820899770544814163379169539926317676679421275092688200844094929042154854719312788471536324082041360841253720783220459009201882865091829118575721525038404689868986360373373122049951274015083845966946475469982961355934516388706446794517870569063777231434618411404965077775991870069073539415961610645268985004687402050059891500490949250730689691141954694508001895390336750734542724392709744200091587065816283592253967715080611459937165344139809223328071517060208
g2 = 14068322834597276347776814624877614869834816383564391664570268934537693322688875343215293618493363798985047779057952636529313879548457643220996398640913517182122425631198219387988691569709691279442005545716133131472147592456812502863851227108284027033557263611949365667779259585770738623603814004666845554284808166195201470503432803440754207350347128045893594280079379926676477680556845095378093693409219131090910168117334308781843178748431526974047817218228075136005979538773141427004682344298827618677773735288946271346252828348742296301538573408254015281232250841148556304927266143397565889649305095857756884049430
c1, c2 = (11823197525493679922462229312577565795790231943088967365041996969833687685138684663425736403362435947961162359880274061507909130337620672558788978473833973219147915805313662825413066312702383051828013250123487196306204170199886569869489424725349908927607008718147223533469811907589117819645863932215575433971043477313368023151369535540404625770972404614353104003800218866798610393931587791320241316614291168862653357565646094135540152539864650862797163818826669760914933822102864027625653527726320652797672561838261305835579141720874114224470663547248330428718333156518891792470511397032487663666074601934673538205109, 2779880537115408257595446644781256096238766529002829447374722026519904649762403856519534823378460053135911559335526959970225428282722454848749344880298922526768059646336181280198446021828944801139755808467391788638452557321859820238241700901109441893986616102072462317079424252804407738823379369895077334731847147033163210247117705503923134257895313179139530926252976334117657503240153146324063219900284664702824599298036943536916560758754916817002800088718757733395590409870811657828057225054151582638807129324477142895521653053887499550733193273834240174306480447726764751838123539992748222035712739618864572963930)
print(long_to_bytes(decrypt(c1, c2)))

加密解密原理

在做的过程中，有一点令我感到疑惑，一开始看到解密函数时，我认为这并不是针对加密函数的；也就是说，我以为的考点是让我们自己实现解密函数的

生成随机数

生成p，q，g1，g2，（g，r1，r2$\in$[1, N]）
$$
g_1=g^{r_1\times(p-1)}\ mod\ N\notag
$$

$$
g_2=g^{r_2\times(q-1)}\ mod\ N\notag
$$

加密

加密后的结果是c1，c2，（s1，s2$\in$[1, N]）
$$
c_1=m\times g_1^{s_1}\ mod\ N\notag
$$

$$
c_2=m\times g_2^{s_2}\ mod\ N\notag
$$

解密

看他的样子是解以下这个同余方程组
$$
m\equiv c_1\ (mod\ p)\notag
$$

$$
m\equiv c_2\ (mod\ q)\notag
$$

顺便再来回顾以下CRT的通式，直接抄维基百科上的了

image-20210706144819994

但问题是m和c满足这个同余方程组吗？就像是ElGamal一样，他乘了一个数，不应该乘以其的逆元吗？

然后尚师傅点醒我了，由$g_1=g^{r_1\times(p-1)}\ mod\ N$可知，
$$
g_1\equiv g^{r_1\times (p-1)}\equiv 1\ (mod\ p)\notag
$$
这就是欧拉定理

所以在模p和模q时，那个加密时多乘的数就变成1了

总之，回到题目，说是一种修改过的RSA加密模式；当然也知道CRT加速RSA的解密，前提是要知道p和q，就和这个异曲同工吧，这种方法有点借鉴了ElGamal加密算法的思想

easy_RSA

题目描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
from random import randint
from gmpy2 import *
from Crypto.Util.number import *

def getprime(bits):
    while 1:
        n = 1
        while n.bit_length() < bits:
            n *= next_prime(randint(1,1000))
        if isPrime(n - 1):
            return n - 1

m = bytes_to_long(b'flag{************************************}')

p = getprime(505)
q = getPrime(512)
r = getPrime(512)
assert m < q

n = p * q * r
e = 0x10001
d = invert(q ** 2, p ** 2)
c = pow(m, 2, r)
cipher = pow(c, e, n)

print(n)
print(d)
print(cipher)


'''

7941371739956577280160664419383740967516918938781306610817149744988379280561359039016508679365806108722198157199058807892703837558280678711420411242914059658055366348123106473335186505617418956630780649894945233345985279471106888635177256011468979083320605103256178446993230320443790240285158260236926519042413378204298514714890725325831769281505530787739922007367026883959544239568886349070557272869042275528961483412544495589811933856131557221673534170105409
7515987842794170949444517202158067021118454558360145030399453487603693522695746732547224100845570119375977629070702308991221388721952258969752305904378724402002545947182529859604584400048983091861594720299791743887521228492714135449584003054386457751933095902983841246048952155097668245322664318518861440
1618155233923718966393124032999431934705026408748451436388483012584983753140040289666712916510617403356206112730613485227084128314043665913357106301736817062412927135716281544348612150328867226515184078966397180771624148797528036548243343316501503364783092550480439749404301122277056732857399413805293899249313045684662146333448668209567898831091274930053147799756622844119463942087160062353526056879436998061803187343431081504474584816590199768034450005448200

'''

解题思路

先看三个素数，这里出题人狡诈，p是用题目中的getprime函数得出来的，q和r则是用Crypto库中的getPrime得到的

所以看函数就知道，p+1可以很好地得到分解

我们求解的步奏一步步反推回去应该是这样

image-20210706161649767

必须知道p和q，然后求出r

直接送去分解

image-20210706162410515

但p确实满足上述性质

image-20210706162852340

那就先按照上面的流程写脚本吧

在最后一个箭头处，由于算来的c是512位的，所以不能对c进行直接开方；那么rabin攻击呢，模数是一个质数，平方根算法登场

脚本编写

用下库函数了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from Crypto.Util.number import *
from gmpy2 import *
from sympy.ntheory.residue_ntheory import nthroot_mod

n = 7941371739956577280160664419383740967516918938781306610817149744988379280561359039016508679365806108722198157199058807892703837558280678711420411242914059658055366348123106473335186505617418956630780649894945233345985279471106888635177256011468979083320605103256178446993230320443790240285158260236926519042413378204298514714890725325831769281505530787739922007367026883959544239568886349070557272869042275528961483412544495589811933856131557221673534170105409
d = 7515987842794170949444517202158067021118454558360145030399453487603693522695746732547224100845570119375977629070702308991221388721952258969752305904378724402002545947182529859604584400048983091861594720299791743887521228492714135449584003054386457751933095902983841246048952155097668245322664318518861440
cipher = 1618155233923718966393124032999431934705026408748451436388483012584983753140040289666712916510617403356206112730613485227084128314043665913357106301736817062412927135716281544348612150328867226515184078966397180771624148797528036548243343316501503364783092550480439749404301122277056732857399413805293899249313045684662146333448668209567898831091274930053147799756622844119463942087160062353526056879436998061803187343431081504474584816590199768034450005448200
e = 0x10001
p = 102634610559478918970860957918259981057327949366949344137104804864768237961662136189827166317524151288799657758536256924609797810164397005081733039415393
q = 7534810196420932552168708937019691994681052660068275906973480617604535381306041583841106383688654426129050931519275383386503174076258645141589911492908993
r = 10269028767754306217563721664976261924407940883784193817786660413744866184645984238866463711873380072803747092361041245422348883639933712733051005791543841
assert d == invert(q**2, p**2)
phi = (p-1)*(q-1)*(r-1)
d = invert(e, phi)
c = pow(cipher, d, n)
# print(c.bit_length())
# 512
# print(c)
# c = 8081092455112516397361105816900490085355315574087538340788309885334106796325593823678787887569920404814986643819898763828872716522338864714182757065213683
print(long_to_bytes(nthroot_mod(c, 2, r)))

光滑数

之前就想整理Crypto中关于光滑数的考点

所谓光滑数就是：是一个可以因数分解为小素数乘积的正整数

然后有两个算法可以分解，一是这道题讲的Williams’p+1 algorithm，还有一种是解减一是光滑数的Pollard’s p−1 algorithm，可以使用这个python的包来解

1
python -m primefac -vs -m=p-1 XXXXX
1
python -m primefac -vs -m=+1 XXXXXX

举个例子

题目描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from random import choice
from Crypto.Util.number import isPrime, sieve_base as primes
from flag import flag


def myPrime(bits):
    while True:
        n = 2
        while n.bit_length() < bits:
            n *= choice(primes)
        if isPrime(n + 1):
            return n + 1

e = 0x10001
m = int.from_bytes(flag.encode(), 'big')
p = myPrime(2048)
q = getPrime(2048)
n = p * q
c = pow(m, e, n)

# n = 1224542620373200232525165378018470774334801515191193204875465445916504222883935188890019876845076388385357911730689547124547346252951158814249284724565588433721828377715469374541007756509231399263095022024229078845538543233785364809917406108015271780070196140628158427541531563472532516237632553353655535922926443707617182025475004547531104052989085765070550150028833424395972178427807901747932614235844448614858629761183210600428438018388051958214596857405813088470933109693499438012040822262549119751099008671892966082341548512112435591881692782766559736840448702039918465573051130405935280702181505538733234675792472428666968900055706926735800561218167237812066851519973807203332801575980055838563085817664973968944323258406789203078387708964307931318918136664885818917720073433998810127482159223895026085726623747340692196977140382318293090736558135980651252533606603312148824142669800602887109353065489282386215179238458743567166284295855288783740314247952124965482197632971993708775190564519250754150756867653033527903848903210074426177258586450311109023467944412194124015505951966140443860862968311560843608415723549525497729679097936310538451467530605937684408079363677707513923579164067808729408365886209340192468399685190639
# c = 145742860621666495489510776707734134231023214235535481878205099324276369445463746101469487674333600296204530932386373415987357363515200117271393133347844479863240936801112306080456942844796779477817786176831015954410967693647534326733641573842953783193563678040093734579772976410574013857063137696465850300484753282472377882118892522844694078667622111244886303620349388556315704648609353412177123230438077637042880490566244740468503369707900343076369151796123461132932226563486870411965536062339169788331659119981901553536009275158600580698576110294775989992794065611215170351808698605911258789407992833170968332058255364527244293283228694886707241979238145252395651417561576433516407782575454294499521347378058366557950770592472271985004818847838711060048422015207674862177145761946560579360220239667890707135827136815780729363013864130107808776517514214310689477005999830284272130148939734935547341627208913181919190392205389452185597444280635342938046191904062547803917870268485346888653569349729643793041018550170090471310374856687407102762116819004790791936814214507908374380597027347007448114684844276041116955473180015221164545212550832233007714133699817366745648092776901013502840540012912660742166994968977400188176557657864

显然p是n-1类型的光滑数，但是直接食用工具，效果不佳

Pollard’s p−1算法

推导步奏

目标很明确，通过p分解n

所谓的Pollard’s p−1算法就是
如果p-1是光滑数，那么n!就能被p-1整除，即n!=t(p-1)
对于n=2,3,4,…，只要
$$
gcd(2^{n!}-1, N)\neq 1和N\notag
$$
就成功分解N了
以上算法适用于p是N的因数，且p-1是光滑数

当然求n的阶乘是个耗费资源的事情，所以我们对递归式子精心简化，这样就不用重复计算了
$$
2^{n!}\ mod\ N=(2^{(n-1)!}\ mod\ N)^{n}\ mod\ N\notag
$$

而由我们熟悉的费马定理可以推出
$$
2^{t(p-1)}\equiv 1\ mod\ p\notag
$$
改写成等式
$$
2^{t(p-1)}-1=kp\notag
$$
所以$2^{t(p-1)}-1$是p的倍数，结合前面推出的，我们得到的结论是
$$
2^{n!}-1=kp\notag
$$
通过枚举n求kp，求kp和N的公因子就是p

也没看得特别懂，得到的递推式子是
$$
2^{n!}\ mod\ N=
\begin{cases}
2^2\ mod\ N& {n=2}\\
(2^{(n-1)!}\ mod\ N)^n\ mod\ N& {n \geq 3}
\end{cases}\notag
$$

写出来的脚本是这样的

1
2
3
4
5
6
7
8
def pollard_p_1(n):
    a = 2
    i = 2
    while gcd(a-1, n) == 1 or gcd(a-1, n) == n:
        a = pow(a, i, n)
        i += 1
    print(i)
    return gcd(a-1, n)

要跑挺久的，虽然也才十几万次

最后得到的flag

1
flag{Pollard_s_p-1_&_William_s_p+1}

Backtrace

题目描述

Can you trace back to the past?

1
2
3
4
5
6
7
8
9
10
11
# !/usr/bin/env/python3
import random


flag = "flag{" + ''.join(str(random.getrandbits(32)) for _ in range(4)) + "}"

with open('output.txt', 'w') as f:
    for i in range(1000):
        f.write(str(random.getrandbits(32)) + "\n")

print(flag)

解题思路

MT19937，它有一千个随机数，需要找到这一千个随机数的前面一个

完整地把MT19937给逆回去就好了，具体参考2022DASCTF MAY 出题人挑战赛

image-20210706221821180