VNCTF_2021_whitegive

总结

根据本题,学习与收获有:

  • 要善于从多个方程组中总结出来未知数和已知数的关系,在同余式中,要善于利用余数、最小公倍数和最大公约数一些性质。大数分解是难题,但是两个大数求解公约数是很快的。
  • 当解密指数d比较小的时候,首先采取wiener attack,倘若解不出来,尝试Boneh Durfee Attack

题目

题目如下:

 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
from Crypto.Util.number import *
from secret import url
from gmpy2 import *

m = bytes_to_long(url)
p = getPrime(512)
q = getPrime(512)
n = p * q
d = getPrime(256)
e = inverse(d,(p-1)*(q-1))
c = pow(m,e,n)

print(n)
print(c)

m = e
p = getPrime(512)
q = getPrime(512)
n = p * p * q
e = 0x10001
d = inverse(e,lcm(p,lcm(p-1,q-1)))
c = pow(m,e,n)
hint = pow(d,e,n)

print(n)
print(c)
print(hint)

'''
97814568264814384858194701955408461509880555772006698372422205341758322175891474378211599333051180365254844248340812534463000531890490435018379585036704801177155418066770861143206836558793774360498040810255823235715535487716966004194143204900564413879660115112965484824906920141847149888933004740523449213441
86143311788363675684674113699193046781796638913243016152555572150858159500527674063754694514501999791875561142925154991000532628799185608465062814546108160434468098898040769021072007374156546314975240583347468026001633652940408779155579339470960571067652924814623371177901052302005289155305089588204204313261
1246903000089073759886267722667196003041462505274526737638837808213476294697746018085346623497511017543801377442390781101585650581984057653018703031659844145960721073451379508212905335383758157379301019575213158532070229897587088955814288202279949391608732448294591675986989254272257059551622461096394217684402667140362275595245430242117193793913872208576714597860532581116390903216389172132085635891741189355461016795362341416848534340615825023292174042406128959
952508462840095293368043281511747192551431448088755251878915582522463097721381421883702408853564036431155676272901680250701398946525803160765527940151587567521509500006089852079864042238196362897144754722623523621230744820970423076092319608853809407595863195726851921082224085255808985329769890887863865121647796115540376158135632760785321953364738008064130705467326745546629505023549047992509562623348749056757848144371814157305011884825502144329268299851210747
788785744509676701442642497798353940704045062680685297430840370664093043099033424646382070232242765761123110381200239132310785932203252095093993313010883982078216697297202940152563278231011836966627537170460186597134847633828107444548759805274516431300662852153808962421740187067058018192457264083227110866080267684557127718769967184710395811547902947248700889674967381917907905535103547918375731341071557144999864774198881339085314424766509424492349867615604684

'''

题目分析

题目经过了两轮RSA加密:

  • 第一轮RSA,注意到pq都是512位,而d只有256位。题目给了nc,没有给e
  • 第二轮RSA,这一轮是对上一轮的e进行加密,给出{% raw %}$e = 65537${% endraw %},给{% raw %}$n = p * p * q${% endraw %},同时给了hint,并且{% raw %}$hint = d^e \pmod {phi}${% endraw %}。

既然给了hint,很显然本题就需要从hint入手来进行分析。结合已知信息,来分解出n。推导其实很简单,利用hint能快速地分解出第二轮RSA加密的n

解题过程

公式推导

首先需要分解出第二轮加密的n,推导如下:

设第二轮加密的相关参数有:nehintpq

已知的有{% raw %}$n = p * p * q${% endraw %}, {% raw %}$e = 65537${% endraw %}, {% raw %}$h${% endraw %}也已知

根据题目设{% raw %}$phi = lcm(p, lcm(p - 1, q -1))${% endraw %}, {% raw %}$ed === 1 \pmod {phi}${% endraw %}

那么有式1{% raw %}$e * d = 1 + k_{1} * p${% endraw %}。这是因为p是质数,那么phi一定是p的倍数。

题目又有{% raw %}$hint = d ^ e \pmod {n}${% endraw %}

所以有式2{% raw %}$d ^ e = hint + k_{2} * p${% endraw %},因为n也是p的倍数

把式1带入到式2中去有:

{% raw %}$(\frac{1 + k_{1} * p} {e})^e = hint + k_{2} * p${% endraw %}

{% raw %}$(1 + k_{1} * p) ^ e = e ^ e *(hint + k_{2} * p)${% endraw %}

这里将上式的左侧展开,可以发现,一定会有一个1,剩下的数也一定是p的倍数,因此有:

{% raw %}$(1 + k_{1} * p) ^ e = 1 + k_{3} * p${% endraw %}

因此有:

{% raw %}$1 + k_{3}*p = e^e * (hint + k_{2} * p)${% endraw %}

整理一下有:

{% raw %}$(k_{3} - k_{2}*e^e) * p = hint * e ^ e -1${% endraw %}

又有:

{% raw %}$n = p * p * q${% endraw %}

合理猜测,pn{% raw %}$hint * e ^ e - 1${% endraw %}的最大公约数。因此可以求{% raw %}$[n, hint * e ^ e -1]${% endraw %},如果是质数,就印证了猜测。

解题步骤

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
import gmpy2
from Crypto.Util.number import long_to_bytes

n = 1246903000089073759886267722667196003041462505274526737638837808213476294697746018085346623497511017543801377442390781101585650581984057653018703031659844145960721073451379508212905335383758157379301019575213158532070229897587088955814288202279949391608732448294591675986989254272257059551622461096394217684402667140362275595245430242117193793913872208576714597860532581116390903216389172132085635891741189355461016795362341416848534340615825023292174042406128959
c = 952508462840095293368043281511747192551431448088755251878915582522463097721381421883702408853564036431155676272901680250701398946525803160765527940151587567521509500006089852079864042238196362897144754722623523621230744820970423076092319608853809407595863195726851921082224085255808985329769890887863865121647796115540376158135632760785321953364738008064130705467326745546629505023549047992509562623348749056757848144371814157305011884825502144329268299851210747
hint = 788785744509676701442642497798353940704045062680685297430840370664093043099033424646382070232242765761123110381200239132310785932203252095093993313010883982078216697297202940152563278231011836966627537170460186597134847633828107444548759805274516431300662852153808962421740187067058018192457264083227110866080267684557127718769967184710395811547902947248700889674967381917907905535103547918375731341071557144999864774198881339085314424766509424492349867615604684
e = 0x10001

tmp1 = hint * pow(e, e) - 1
p = gmpy2.gcd(n, tmp1)
assert gmpy2.is_prime(p), "p is not prime!"
print("p: ", p)

最后输出为:

1
# p:  12277650054115967661107194664489294899976814835828734682974752510058202849445626179849053725591557564741699546987225940819984218689690122416052643452524421

可知,猜想是正确的。

那么就,解出上一轮加密使用的e

1
2
3
4
5
6
7
8
9
q = n // p // p
phi = gmpy2.lcm(p, gmpy2.lcm(p -1, q - 1))
d = gmpy2.invert(e, phi)

m = pow(c, d, n)

print("last round e: ", m)

# e = 93943500165298065499950418373429723509334252629406924973909070866091749987346174290549648466771963135864917881154270768788129489671486923171733460927672763251885052132144244633336183737015936611716827476566876619327956203686756399730968768494676888428137426449681845021696056187478027217734766494935085365973

接着,来解出第一轮加密的明文。wiener attack解不出来,得用Boneh Durfee attack

有:

image-20210502135241702

那么就解出了第一轮加密的密文为:

1
2
3
4
5
6
7
n0 = 97814568264814384858194701955408461509880555772006698372422205341758322175891474378211599333051180365254844248340812534463000531890490435018379585036704801177155418066770861143206836558793774360498040810255823235715535487716966004194143204900564413879660115112965484824906920141847149888933004740523449213441
c0 = 86143311788363675684674113699193046781796638913243016152555572150858159500527674063754694514501999791875561142925154991000532628799185608465062814546108160434468098898040769021072007374156546314975240583347468026001633652940408779155579339470960571067652924814623371177901052302005289155305089588204204313261

# Boneh Durfee attack
d0 = 103079922798932082066165266087442072203677117380612800709240732626110126828541
m0 = pow(c0, d0, n0)
print("m0:", long_to_bytes(m0)) # b'https://dawn-whisper.lanzous.com/iCAv0lod7yj-password:gzjq'

是一个网址,下载下载,得到第二关的题目,老套娃了:

 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
# Wow, you got here!
# This is the last task, trust me!
from Crypto.Util.number import *
from secret import flag,padding
from gmpy2 import *

m = bytes_to_long(flag)
e = 7 

p = getPrime(512)
q = getPrime(512)
n = p * q

c1 = pow(m,e,n)
c2 = pow(m+padding,e,n)

print(n)
print(c1)
print(c2)

'''
143224951702807798608353389056046982493788310072914995404719898237226283884553121669729599925829562704800197375580487019006702401282671268969358774635337351738915083955659230582177495821699251999928502338923489031347921151957398310960671307216790020399224115377846788378990638367296298663795893865325304226511
74797173657575640598140788410852016843612519588375968190579734420951374103129570637822547217967978911328419808529204143522454142303138959013220811558490951614314306849367068478190797885056922705403028856734095288522290055309880572321557493798362056216783777593386133347693892941928131945986087712737862263761
9209695919437085323423940852135308337887271742988391422139555924185234849146079306139570263602339983687993333013333937719071267190971983543492940032646907167417161479697805991443259327402389097539126399994414628326218438416138199892253597375493026563369334352434282120293396846427418323600336867792587721214

'''

读下题目,就是related message attack,使用[脚本](CTF-Crypto/FranklinReiter.sage at master · ValarDragon/CTF-Crypto (github.com))即可跑出答案。

image-20210502140210528

最后解得flagVNCTF{H4ppyNeWy34r!2021_V&N_figHt1ng!}

引用与参考

Buy me a coffee~
roderick 支付宝支付宝
roderick 微信微信
0%