Harry's Blog

温故知新

0%

寒假修炼记（二）

发表于 更新于   阅读次数： Valine：
本文字数： 102k 阅读时长 ≈ 1:33
“匕首反握，杀死懒惰”，这里是自2022年1月5日开始的每日记录🐛

1.5

课程

RSA·dp、dq泄漏

什么是dp、dq

dp = d mod (p-1)
dq = d mod (q-1)

重要结论

当m < p 或 q时

m<p:

$$ m = c^d \mod p$$

$$ m = c ^ {dp} \mod p $$

m<q:

$$ m = c^d \mod q$$

$$ m = c ^ {dp} \mod p $$

证明

image-20220105105634124

代码实现
1
m = pow(c, dp, p)

更一般的

已知条件
c = m^e mod n
m = c^d mod n
ϕ(n)= (p−1)(q−1)
de≡ 1 mod ϕ(n)
dp= d mod (p−1)
dq= d mod (q−1)

m=c^d mod n
m=c^d+k*n

因为 n=pq
m=c^d+pq*k

同时取余q和p

式1 m1=c^d mod q
式1 c^d=kp+m1

式2 m2=c^d mod p

式1带入式2
m2=(kp+m1) mod q

等式两边同时减去m1
(m2−m1)≡kp mod q

因为gcd(p,q)=1
所以可以求p的逆元，得到
(m2−m1)*p−1≡k mod q

得到如下两个式子
k≡(m2−m1)*p−1 mod q

c^d=kp+m1
m≡c^d mod n

上下两个式子合并

c^d = ((m2−m1)*p−1 mod q)p+m1
m ≡ c^d mod n

最后可以有

m≡(((m2−m1)*p−1 mod q)p+m1) mod n

只剩最后一步了

m1≡cd mod q
m2≡cd mod p

m1和m2怎么求

d≡dp mod (p−1)
d≡dq mod (q−1)

那么分别带入

m1≡cdq mod (q−1) mod q
m2≡cdp mod (p−1) mod p

费马小定理即假如p是质数，且gcd(a,p)=1
a^(p−1)≡1 mod p

所以如果我们有等式

d=dp+k*(p−1)

直接带入
m2≡c^dp+k*(p−1) mod p

这里的指数，我们拆开，为
m2≡c^dpck(p−1) mod p

ck*(p−1)≡1 mod p

因为p是大素数，显然和c互素所以可以直接得到
m2≡cd^p mod p

那么m1根据对称性也可以同理得到

m1≡cd^q mod q

故此，我们现在拥有了所有条件，下面归纳一下为

m1≡cd^q mod q
m2≡cd^p mod p
m≡(((m2−m1)*p−1 mod q)p+m1) mod n

代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# coding=utf-8
import gmpy2
import libnum

def decrypt(dp,dq,p,q,c):
    InvQ = gmpy2.invert(q, p)
    mp = pow(c, dp, p)
    mq = pow(c, dq, q)
    m = (((mp-mq)*InvQ) % p)*q+mq
    print(libnum.n2s(int(m)).decode())

p= 160332148422085773419118366054725936852233416334843123745197905865814122767542980683547268180832158164485150298039693727719040683372172258525148659296087240380682418673910965969383538696724039000114078510939033236731476700182949760779821042982194738324421029616780752077145649691266297077244661585947836997447
q= 148424511925430832355285085986622242653116164650119278601839811809456838348201308360579207172541711367335049779204390510911294031319604192881139002646252381246691575112024047502962776542023275076827456857946499013733968522162634588753330857821421229306405469212854327011240808908334404955299250060931240865821
dq= 46499718919891753512042256824043332562579628188599554881257534157373206051013462063558177543473555667701042801266834703603013397791386747764400964376350060145521940586234916815399419075649204020285050341140996959732454059493770135591854817473937175643058380668604376797759987312600851466228301604453060674993
dp= 142333710655003285129381975633061553108365353347897720974344479656881847851071160049571693284111493690735707224010091720382284617217647771503015838348510851051285580945849520119912938971503190396671148935203517916795662212439446680229030750273953490024181996476865040448118374338738013091140796970725623029913
c= 19717919131356145411002342007533511479254120775597684622452661875292805564648015749422307039514664862428413419529876049533096947970606477676695854787457286807502628964582922773374784879459806551819337741730331777937597915727889640104583136339578788518904647309084873362461758500783634423921343109980901514994298280728150961559886893338458119937441920391275957965781890308011172861718172757876950159723089326843019779174406022143147201642738466470809603008292152193968160973116769118512212438656127645018486302418482079051867180606083540035964208124143457540388206274742292869004756069240519187723267661857029470809099


decrypt(dp,dq,p,q,c)

RSA·n是p的r次方

当$ n = p^{r} $时

$$ phi = p^r - p^{r-1} $$

比较简单，在rsa原理学习就已经提及，略。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import libnum 
import gmpy2 


n=23219089633250510580388184338893261190159425274266091829251069678345101374315005119889075848991325948461687799542168350589180122396501651434531030343667226410506241902501479054317717625217008857112114881864252928341340770771920275461651508679148124345837511394681152499950625703121385320234450147885925563601 

e= 65537 

c=4777659110099869449331032200405354033599223023041765916601886190091487314989244505694085724093454432510462782520998688417537643026221506529296297782026160739262075190691284018675189858368054339063575534858807322887095235742287437139426799368719305846674897884286541494038433345483824310623372192122891409065 #分解n #yafu-x64.exe factor() 

p=69416273731307471601239913553838998413594935515871627319658832112504691596643 

phi_n=p**4-p**3
d=libnum.invmod(e,phi_n) 
m=pow(c,d,n)
print(libnum.n2s(int(m)).decode())

当$ n = p^{r}·q^{s} $时

RSA原理学习篇中，已知：

如果n可以分解成两个*互质的整数之积*，n = p1 × p2*，则*：

φ(n) = φ(p1p2) = φ(p1)φ(p2)

所以φ(n) =φ($p^{r} $) · φ($q^{s} $)

$$ φ(n) = (p^{r} - p^{r-1})*(q^{s} - q^{s-1}) $$

通常为了计算方便，公因式提出来。

例子

$$ n = p^{3}*q $$

易知：$ φ(n) = (p^{3} - p^{2})*(q-1) $

提公因式 $ p^2 $,得：

$$ φ(n) = (p-1)p^{2}(q-1) $$

之后就是常规的求解，略。

RSA·n分解为多个素数

结论

例： n = p* q * r

则φ(n) = φ(pqr) = φ(p)φ(q)φ(r)=(p-1)(q-1)(r-1)

原理

如果n可以分解成两个*互质的整数之积*，n = p1 × p2，则：
**φ(n) = φ(p1p2) = φ(p1)φ(p2)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import libnum
import gmpy2
#生成随机素数
p=libnum.generate_prime(32)
q=libnum.generate_prime(32)
r=libnum.generate_prime(512)
e=65537
m="flag{20d6e2da95dcc1fa5f5432a436c4be18}"
#字符串转数字
m=libnum.s2n(m)
n=p*q*r
phi_n=(p-1)*(q-1)*(r-1)
#求逆元
d=libnum.invmod(e,phi_n)
c=pow(m,e,n)
print ("n=",n)
print ("e=",e)
print ("c=",c)

RSA·e和phi不互素

e和phi不互素，这是一个严重的问题。

在rsa原理学习篇中，也有说到：e得与phi互素

否则,求不出e的逆元d

没有私钥d，求解rsa便是无稽之谈了

对策

总体而言，两字：构造

  1. 先找到e与phi的公约数

    t1 = gcd(e, phi)

  2. 得到与phi互素的t2

    t2 = e // t1

  3. t1、t2代入

    $ c = m^{e}modn = (m^{t1})^{t2}modn$

  4. $ m^{t1} $当作新的明文M；t2当作新的加密指数E，则有：

    $ c = M^{E}modn $

t2(E)与phi互素，通过构造，问题已经变得常规了。

最后，对解出的M开t1次方，即得m.

代码实现

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


# 当e约去公约数后与phi互素
def decrypt(p, q, e, c):
    n = p * q
    phi = (p - 1) * (q - 1)
    t = gmpy2.gcd(e, phi)
    d = gmpy2.invert(e // t, phi)
    m = pow(c, d, n)
    print(m)
    msg = gmpy2.iroot(m, t)
    print(msg)
    if msg[1]:
        print(long_to_bytes(msg[0]))

p= 127577058764408216374028752283743628765651360507566484643526093715329608267323381565274095814069864692746147152580906850350743742856555229701448239882612922698102985146366639955081466129923966803267071097174222576416224094182123529282235807472362341680183683025490897702891081336913842652559163341223338641607
q= 156492273708587234539506501480609692085997989594717058472605523051244522493701609615085173280972894139427194976925940854142835807192417391269823151398439665817176522629246535810290194301862945052149450578938260979300632842291287807430486629994530805358742405299538986591596966945727494262182814875780600646003
e= 750
c= 7029383721249299532521086933490698266831518266762255492452526410777276825803657150303837084263410309063739203644435184397762022380085273363900423091223180151147964276354189658062571415744140073426572149093499560918765793389358300893454490774387180728097370701432534877005948330689495694820361726719418371072834639369078180094444137972424909816959445043108154884587947573054460257114169961823509538355580857411319157089278918107229480661280354242839678709689654304688727345294473487201644985815128413154870914132135222144633969959773621933444285994038028721862094040876152694240238708737727034258171506516394913692187

decrypt(p, q, e, c)

RSA·NC不互素

题型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 2021绿城杯·RSA-1
from Crypto.Util.number import *
import gmpy2
from flag import flag
assert flag[:5]==b'flag{'

m = bytes_to_long(flag)
p = getPrime(1024)
q = getPrime(1024)
n = p * q
print('n =',n)
e = 0x10001
M = 2021 * m * 1001 * p
c = pow(M,e,n)
print('c =',c)

#n = 17365231154926348364478276872558492775911760603002394353723603461898405740234715001820111548600914907617003806652492391686710256274156677887101997175692277729648456087534987616743724646598234466094779540729413583826355145277980479040157075453694250572316638348121571218759769533738721506811175866990851972838466307594226293836934116659685215775643285465895317755892754473332034234495795936183610569571016400535362762699517686781602302045048532131426035260878979892169441059467623523060569285570577199236309888155833013721997933960457784653262076135561769838704166810384309655788983073376941843467117256002645962737847
#c = 6944967108815437735428941286784119403138319713455732155925055928646536962597672941805831312130689338014913452081296400272862710447207265099750401657828165836013122848656839100854719965188680097375491193249127725599660383746827031803066026497989298856420216250206035068180963797454792151191071433645946245914916732637007117085199442894495667455544517483404006536607121480678688000420422281380539368519807162175099763891988648117937777951069899975260190018995834904541447562718307433906592021226666885638877020304005614450763081337082838608414756162253825697420493509914578546951634127502393647068722995363753321912676

结论

  • 当加密方式为：

    $$ c = (m*p)^{e}modn $$

  • 有：p = gcd(n, c)

    即：当n，c不互素时，它们的最大公约数必然是p

证明

  1. 由$ c = (m*p)^{e}modn $，得:

    c = $ (m*p)^{e} - kn $

  2. 两边同时模p，则：

    $$ c \mod p = (m•p)^{e} \mod p = ((m•p)\mod p)^{e} \mod p =[(m \mod p)•(p\mod p)]\mod p)^{e}\mod p $$

  3. 由$ p \mod p = 0 $，得：

    $$ c \mod p = 0$$

    即： c = kp

  4. 因为n = pq，所以有：

    gcd(n, c) = p

    代码求解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import gmpy2
import libnum

n = 17365231154926348364478276872558492775911760603002394353723603461898405740234715001820111548600914907617003806652492391686710256274156677887101997175692277729648456087534987616743724646598234466094779540729413583826355145277980479040157075453694250572316638348121571218759769533738721506811175866990851972838466307594226293836934116659685215775643285465895317755892754473332034234495795936183610569571016400535362762699517686781602302045048532131426035260878979892169441059467623523060569285570577199236309888155833013721997933960457784653262076135561769838704166810384309655788983073376941843467117256002645962737847
c = 6944967108815437735428941286784119403138319713455732155925055928646536962597672941805831312130689338014913452081296400272862710447207265099750401657828165836013122848656839100854719965188680097375491193249127725599660383746827031803066026497989298856420216250206035068180963797454792151191071433645946245914916732637007117085199442894495667455544517483404006536607121480678688000420422281380539368519807162175099763891988648117937777951069899975260190018995834904541447562718307433906592021226666885638877020304005614450763081337082838608414756162253825697420493509914578546951634127502393647068722995363753321912676
e = 0x10001
p = gmpy2.gcd(n, c)
q = n // p
assert n == p * q
phi_n=(p-1)*(q-1)
d=gmpy2.invert(e,phi_n)
M=pow(c,d,n)
#M= 2021 * 1001 * p*m
m=M//(2021 * 1001 * p)
print(libnum.n2s(int(m)))

RSA·rabin算法

特征

e = 2

代码

  • 直接给了参数

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    from gmpy2 import *
    import libnum
    import hashlib
    p=275127860351348928173285174381581152299
    q=319576316814478949870590164193048041239
    n=87924348264132406875276140514499937145050893665602592992418171647042491658461
    e=2
    c=45617141162985597041928941111553655146539175146765096976546144304138540198644
    inv_p = invert(p, q)
    inv_q = invert(q, p)
    mp = pow(c, (p + 1) // 4, p)
    mq = pow(c, (q + 1) // 4, q)
    a = (inv_p * p * mq + inv_q * q * mp) % n
    b = n - int(a)
    c = (inv_p * p * mq - inv_q * q * mp) % n
    d = n - int(c)
    #因为rabin 加密有四种结果，全部列出。
    aa=[a,b,c,d]
    for i in aa:
        print(i)
        print(libnum.n2s(int(i)))

  • 文件形式

    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
    from Crypto.PublicKey import RSA
    import libnum
    import gmpy2
    #导入公钥
    with open("pubkey.pem","rb") as f:
        key = RSA.import_key(f.read())
        n =key.n
        e =key.e
    #导入密文
    with open("flag","rb") as f:
        c=libnum.s2n(f.read())

    print(n)
    print(e)
    #n 在线分解
    p=275127860351348928173285174381581152299
    q=319576316814478949870590164193048041239
    inv_p = gmpy2.invert(p, q)
    inv_q = gmpy2.invert(q, p)
    mp = pow(c, (p + 1) // 4, p)
    mq = pow(c, (q + 1) // 4, q)
    a = (inv_p * p * mq + inv_q * q * mp) % n
    b = n - int(a)
    c = (inv_p * p * mq - inv_q * q * mp) % n
    d = n - int(c)
    #因为rabin 加密有四种结果，全部列出。
    aa=[a,b,c,d]
    for i in aa:
        # print(i)
        print(libnum.n2s(int(i)))

1.6/1.7

一月六日，找到并尝试改了了第二届BMZCTF赛的题解的格式

Sage

M1 macOS·Sage安装

参考资料

Sage下载安装学习

Install conda

官网上没有直接给出M1 Mac版本的SageMath二进制安装文件，不过给出了使用conda安装Sage的方法，参考Install from conda-forge。

所以如果自己的Mac上还没有安装conda的话，可以先安装一下，然后使用conda安装SageMath。

首先下载Miniforge3-MacOSX-arm64.sh，cd进入Miniforge3-MacOSX-arm64.sh所在的目录。

Mentioned files - -
Miniforge3-MacOSX-arm64.sh 本地下载 腾讯微云 
1
bash Miniforge3-MacOSX-arm64.sh

接着一路回车，直到确认条款：

1
2
Do you accept the license terms? [yes|no]  
[no] >>> yes

然后编辑配置文件vim ~/.zshrc，在最下面加入如下内容：

1
2
path=('/Users/「这里替换成Mac用户名」/miniforge3/bin' $path)  
export PATH

先按esc键，后输入 wq保存并退出，然后source ~/.zshrc，conda info应该就可以看到了，到这里conda安装完成。

在终端输入下面这些，给conda换到清华源，这样在使用国内网络不走代理的情况下安装一些东西就更快了：

1
2
3
4
5
6
7
conda config --add channels https://mirrors.ustc.edu.cn/anaconda/pkgs/main/  
conda config --add channels https://mirrors.ustc.edu.cn/anaconda/pkgs/free/  
conda config --add channels https://mirrors.ustc.edu.cn/anaconda/cloud/conda-forge/  
conda config --add channels https://mirrors.ustc.edu.cn/anaconda/cloud/msys2/  
conda config --add channels https://mirrors.ustc.edu.cn/anaconda/cloud/bioconda/  
conda config --add channels https://mirrors.ustc.edu.cn/anaconda/cloud/menpo/  
conda config --set show_channel_urls yes

然后输入conda config --show | grep https可以看到已经更新成功的上面的链接。

如果是直接新开的终端，直接输入conda是没有反应的，需要先source ~/.zshrc一下。

Install SageMath

1
2
3
4
5
6
conda config --append channels conda-forge
conda config --set channel_priority strict
conda create -n sage sage python=3.9

# Proceed ([y]/n)? y
# 然后就开始下载安装了

M1 macOS·Sage运行

这时输入conda activate sage，然后输入sage就可以看到sage启动了，也可以使用sage xxx.sage来执行一个sage脚本，这样就是安装完成了。

注意每次启动都需要先conda activate sage进入sage。

Sage·交互模式

conda activate sage后输入sage

Sage·网页模式（推荐

conda activate sage后输入sage -n

image-20220107193401892

1.8

m高位

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
import libnum
def phase2(high_m, n, c):
    R.<x> = PolynomialRing(Zmod(n), implementation='NTL')
    m = high_m + x
    M = m((m^3 - c).small_roots()[0])
    print(libnum.n2s(int(M)))

n= 16375911057984467860173028499662793813198989070891462046702689271326139635781678292779095962528585009670015786235494254339716198163498114440710970519760731615457538963588012609421435357625310123852269659556877780556282784378911243624799312161395869291700339099744622787092292212808041739935363726641015733082591519285930439717736591210957039387077203590963514630879038078615201950805057733038622070074246926048776699133348654093003217709061073510046710565744672093957004519016895478465918909294337641778357708633353664132944153092793959582685432330892190960961439661225639169934805918097911051922729785720701933534021
e= 3
c= 175676150266403934024028881165956357569100114594293998449367661494592439256350774016927790942005197030835672661768700955232102741828268826317608643103085037913845664530507219457425306700667637263739558920826441431873842792152100711788904901597274447160613809337879563457097769364821425046114008763402341
high_m= 56006392793404656900162277604003911130977996870658599363889243117614813715239971694356275604343488512

phase2(high_m, n, c)

p高位攻击

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
n = 22127806011633861727954101002390179580447625543207045612671617864341845851658260004006826435219665722338399712799144283442305160095371386129132285556214330279867129279885732638085139970894386809975772641941102438472230541606849251235636928502018782288977994793382547376630461074356449893196487276906629063423071245785206275636191377977712166746567658967286739276282635616277590864547265366547379387583014365390660407286148179073747800137068237371705680826025177248889969809158386539617738762070772471531610084135064141878988874470291949704156926711239213996266350299670204058121040684469621186909795304289942430452869
p4=0xd8bf1376aaae63b3c4d693ca7f3d8a76270b7310bb8bd4608a98c9fdd85fc1ccc7c246b364e2779034057f0ec7a101bad64269d9dcca69f9b5c3462b058b94db0987aa09426c5e7634b3e19f56872693206790c6feef0c9ae662d73f1b12c3cd
e = 0x10001
pbits = 1024
kbits = pbits - p4.nbits()
print(p4.nbits())
p4 = p4 << kbits
PR.<x> = PolynomialRing(Zmod(n))
f = x + p4
roots = f.small_roots(X=2^kbits, beta=0.4)
if roots:
    p = p4+int(roots[0])
    print ("n: ", n)
    print ("p: ", p)
    print ("q: ", n/p)

至今

键盘之争 · 84

题目

你听说过键盘之争吗？提交你找到的字符串md5值。

ypau_kjg;”g;”ypau+

好的，👀看了半天，啥也没看出来

题解

键盘布局有qwerty、dvorak、colemak
此题考察的是将qwerty布局转为dvorak

img

代码实现

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
import hashlib

dic={r"'":"q",
 
r",":"w",
 
r".":"e",
 
"p":"4",
 
"y":"t",
 
"f":"y",
 
"g":"u",
 
"c":"i",
 
"r":"o",
 
"l":"p",
 
r"/":r"[",
 
r"=":r"]",
 
r'"':'Q',
 
r"<":"W",
 
r">":"E",
 
"P":"R",
 
"Y":"T",
 
"F":"Y",
 
"G":"U",
 
"C":"I",
 
"R":"O",
 
"L":"P",
 
r"?":r"{",
 
r"+":r"}",
 
"a":"a",
 
"A":"A",
 
"o":"s",
 
"O":"S",
 
"e":"d",
 
"E":"D",
 
"u":"f",
 
"U":"F",
 
"i":"g",
 
"I":"G",
 
"d":"h",
 
"D":"H",
 
"h":"j",
 
"H":"J",
 
"t":"k",
 
"T":"K",
 
"n":"l",
 
"N":"L",
 
"s":";",
 
"S":":",
 
r"-":r"'",
 
r'_':r'"',
 
r";":"z",
 
r":":"Z",
 
"q":"x",
 
"Q":"X",
 
"j":"c",
 
"J":"C",
 
"k":"v",
 
"K":"V",
 
"x":"b",
 
"X":"B",
 
"b":"n",
 
"B":"N",
 
"m":"m",
 
"M":"M",
 
"w":r",",
 
"W":r"<",
 
"v":r".",
 
"V":r">",
 
"z":r"/",
 
"Z":r"?",
 
r'!':"!",
 
r"@":r"@",
 
r"#":r"#",
 
r"$":r"$",
 
r"%":r"%",
 
r"^":r"^",
 
r"&":r"&",
 
r"*":r"*",
 
r"(":r"(",
 
r")":r")",
 
r"[":r"-",
 
r"]":r"=",
 
r"{":r"_",
 
r"}":r"+"}
 
s=r'ypau_kjg;"g;"ypau+'
for i in s:
	print (" ".join([key for key, value in dic.items() if value == i]),end='')

m = hashlib.md5()

m.update(*b*'this_is_flag')

print("flag{" + m.hexdigest() + "}")

easy_CRC · 92

题目

1:C4E68E3A
2:08FF301C
3:F6FBA587
4:B85C2F9A
5:F1B73D20
6:C6F1D9D7

flag=1+2+3+4+5+6
Each serial number consists of 4 characters

题解

已知明文长度的CRC爆破，具体学习可见：Python·CRC爆破学习

代码

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
import binascii
import string

# 四字节爆破
def crack_crc():
    print('-------------Start Crack CRC-------------')
    crc_list = [0xC4E68E3A, 0x08FF301C, 0xF6FBA587, 0xB85C2F9A, 0xF1B73D20, 0xC6F1D9D7]  # 文件的CRC32值列表，注意顺序
    comment = ''
    chars = string.printable
    for crc_value in crc_list:
        for char1 in chars:
            for char2 in chars:
                for char3 in chars:
                    for char4 in chars:
                        res_char = char1 + char2 + char3 + char4#获取遍历的任意4Byte字符
                        char_crc = binascii.crc32(res_char.encode())#获取遍历字符的CRC32值
                        calc_crc = char_crc & 0xffffffff#将遍历的字符的CRC32值与0xffffffff进行与运算
                        if calc_crc == crc_value:#将获取字符的CRC32值与每个文件的CRC32值进行匹配
                            print('[+] {}: {}'.format(hex(crc_value),res_char))
                            comment += res_char
    print('-----------CRC Crack Completed-----------')
    print('Result: {}'.format(comment))

if __name__ == '__main__':
    crack_crc()
    """
    -------------Start Crack CRC-------------
[+] 0xc4e68e3a: b323
[+] 0x8ff301c: 1e94
[+] 0xf6fba587: f045
[+] 0xb85c2f9a: e76e
[+] 0xf1b73d20: 5932
[+] 0xc6f1d9d7: 66f4
-----------CRC Crack Completed-----------
Result: b3231e94f045e76e593266f4
    """

rsa · 97

题目

4153372421328787064168548641845708183921443446990158572506114559735441950501706984118235944441928889749083563790293558028143373121367441549974248211570336802004821051820943229232421937298269855190652251294220483768084460779714162849925877879859830009443131489814222929347727735616113359695228615432020363240247474622132986939108457393618346100033147945959684443762976681454755482192433993286205527003029269574787026484389622816932835184754540312561890719407986296481186847292967270288752616

[AFCTF2018]MagicNum

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#72065910510177138000000000000000.000000
c1=0b0110000101100110011000110111010000111101#这里把后面的0给去掉了，本来有64位
#71863209670811371000000.000000
c2=0b0110011001111011011100110110010100111101
#18489682625412760000000000000000.000000
c3=0b0110001101011111011010010111001100111101
#72723257588050687000000.000000
c4=0b0101111101100101011101100110010100111101
#4674659167469766200000000.000000
c5=0b0111001001111001011101110110100000111101
#19061698837499292000000000000000000000.000000
c6=0b0110010101110010011001010111110100111101
import binascii
flag=b''
for i in range(1,7):
    s='c'+str(i)
    print(binascii.unhexlify(hex(eval(s))[2:]))
    flag+=binascii.unhexlify(hex(eval(s))[2:])
print(flag)

[AFCTF2018]你听过一次一密么？

题目

1
2
3
4
5
6
7
8
9
10
11
25030206463d3d393131555f7f1d061d4052111a19544e2e5d
0f020606150f203f307f5c0a7f24070747130e16545000035d
1203075429152a7020365c167f390f1013170b1006481e1314
0f4610170e1e2235787f7853372c0f065752111b15454e0e09
081543000e1e6f3f3a3348533a270d064a02111a1b5f4e0a18
0909075412132e247436425332281a1c561f04071d520f0b11
4116111b101e2170203011113a69001b475206011552050219
041006064612297020375453342c17545a01451811411a470e
021311114a5b0335207f7c167f22001b44520c15544801125d
06140611460c26243c7f5c167f3d015446010053005907145d
0f05110d160f263f3a7f4210372c03111313090415481d49

题解

  • 一次一密：异或加密。

    将明文分组，与密钥按位异或即可。

  • 攻击原理

    题目是用同一个密钥去加密多条明文，当密文条数较多时就很容易被攻击，例如Many Time Pad。

    • Many Time Pad攻击

      原理:c1⊕c2 = m1⊕m2.

      通过m1⊕m2可以分析出m1和m2，因此m1与m2不再安全。

      注：⊕为异或符号

代码

搬运自Github

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#!/usr/bin/python
## OTP - Recovering the private key from a set of messages that were encrypted w/ the same private key (Many time pad attack) - crypto100-many_time_secret @ alexctf 2017
# Original code by jwomers: https://github.com/Jwomers/many-time-pad-attack/blob/master/attack.py)

import string
import collections
import sets, sys

# 11 unknown ciphertexts (in hex format), all encrpyted with the same key

c1='25030206463d3d393131555f7f1d061d4052111a19544e2e5d'
c2='0f020606150f203f307f5c0a7f24070747130e16545000035d'
c3='1203075429152a7020365c167f390f1013170b1006481e1314'
c4='0f4610170e1e2235787f7853372c0f065752111b15454e0e09'
c5='081543000e1e6f3f3a3348533a270d064a02111a1b5f4e0a18'
c6='0909075412132e247436425332281a1c561f04071d520f0b11'
c7='4116111b101e2170203011113a69001b475206011552050219'
c8='041006064612297020375453342c17545a01451811411a470e'
c9='021311114a5b0335207f7c167f22001b44520c15544801125d'
c10='06140611460c26243c7f5c167f3d015446010053005907145d'
c11='0f05110d160f263f3a7f4210372c03111313090415481d49'
ciphers = [c1, c2, c3, c4, c5, c6, c7, c8, c9, c10, c11]
# The target ciphertext we want to crack
#target_cipher = "0529242a631234122d2b36697f13272c207f2021283a6b0c7908"

# XORs two string
def strxor(a, b):     # xor two strings (trims the longer input)
    return "".join([chr(ord(x) ^ ord(y)) for (x, y) in zip(a, b)])

def target_fix(target_cipher):
    # To store the final key
    final_key = [None]*150
    # To store the positions we know are broken
    known_key_positions = set()

    # For each ciphertext
    for current_index, ciphertext in enumerate(ciphers):
        counter = collections.Counter()
        # for each other ciphertext
        for index, ciphertext2 in enumerate(ciphers):
            if current_index != index: # don't xor a ciphertext with itself
                for indexOfChar, char in enumerate(strxor(ciphertext.decode('hex'), ciphertext2.decode('hex'))): # Xor the two ciphertexts
                    # If a character in the xored result is a alphanumeric character, it means there was probably a space character in one of the plaintexts (we don't know which one)
                    if char in string.printable and char.isalpha(): counter[indexOfChar] += 1 # Increment the counter at this index
        knownSpaceIndexes = []

        # Loop through all positions where a space character was possible in the current_index cipher
        for ind, val in counter.items():
            # If a space was found at least 7 times at this index out of the 9 possible XORS, then the space character was likely from the current_index cipher!
            if val >= 7: knownSpaceIndexes.append(ind)
        #print knownSpaceIndexes # Shows all the positions where we now know the key!

        # Now Xor the current_index with spaces, and at the knownSpaceIndexes positions we get the key back!
        xor_with_spaces = strxor(ciphertext.decode('hex'),' '*150)
        for index in knownSpaceIndexes:
            # Store the key's value at the correct position
            final_key[index] = xor_with_spaces[index].encode('hex')
            # Record that we known the key at this position
            known_key_positions.add(index)

    # Construct a hex key from the currently known key, adding in '00' hex chars where we do not know (to make a complete hex string)
    final_key_hex = ''.join([val if val is not None else '00' for val in final_key])
    # Xor the currently known key with the target cipher
    output = strxor(target_cipher.decode('hex'),final_key_hex.decode('hex'))

    print "Fix this sentence:"
    print ''.join([char if index in known_key_positions else '*' for index, char in enumerate(output)])+"\n"

    # WAIT.. MANUAL STEP HERE 
    # This output are printing a * if that character is not known yet
    # fix the missing characters like this: "Let*M**k*ow if *o{*a" = "cure, Let Me know if you a"
    # if is too hard, change the target_cipher to another one and try again
    # and we have our key to fix the entire text!

    #sys.exit(0) #comment and continue if u got a good key

    target_plaintext = "cure, Let Me know if you a"
    print "Fixed:"
    print target_plaintext+"\n"

    key = strxor(target_cipher.decode('hex'),target_plaintext)

    print "Decrypted msg:"
    for cipher in ciphers:
        print strxor(cipher.decode('hex'),key)

    print "\nPrivate key recovered: "+key+"\n"
    
for i in ciphers:
    target_fix(i)

Buuctf · Crypto

RSA1

题目

1
2
3
4
5
p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229 
q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469 
dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929 
dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041 
c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852

题解

明显可见，dp、dq泄漏。

上代码

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import gmpy2
import libnum

p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229
q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469
dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929
dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041
c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852


I = gmpy2.invert(q, p)
mp = pow(c, dp, p)
mq = pow(c, dq, q)               #求幂取模运算

m = (((mp-mq)*I)%p)*q+mq       #求明文公式
print(libnum.n2s(int(m)))
# b'noxCTF{W31c0m3_70_Ch1n470wn}'

old-fashion

题目

1
Os drnuzearyuwn, y jtkjzoztzoes douwlr oj y ilzwex eq lsdexosa kn pwodw tsozj eq ufyoszlbz yrl rlufydlx pozw douwlrzlbz, ydderxosa ze y rlatfyr jnjzli; mjy gfbmw vla xy wbfnsy symmyew (mjy vrwm qrvvrf), hlbew rd symmyew, mebhsymw rd symmyew, vbomgeyw rd mjy lxrzy, lfk wr dremj. Mjy eyqybzye kyqbhjyew mjy myom xa hyedrevbfn lf bfzyewy wgxwmbmgmbrf. Wr mjy dsln bw f1_2jyf-k3_jg1-vb-vl_l

题解

quipqiup爆破,得到结果

image-20220112191539049

flag{n1_2hen-d3_hu1-mi-ma_a}

RSA3

题目

1
2
3
4
5
c1=22322035275663237041646893770451933509324701913484303338076210603542612758956262869640822486470121149424485571361007421293675516338822195280313794991136048140918842471219840263536338886250492682739436410013436651161720725855484866690084788721349555662019879081501113222996123305533009325964377798892703161521852805956811219563883312896330156298621674684353919547558127920925706842808914762199011054955816534977675267395009575347820387073483928425066536361482774892370969520740304287456555508933372782327506569010772537497541764311429052216291198932092617792645253901478910801592878203564861118912045464959832566051361
n=22708078815885011462462049064339185898712439277226831073457888403129378547350292420267016551819052430779004755846649044001024141485283286483130702616057274698473611149508798869706347501931583117632710700787228016480127677393649929530416598686027354216422565934459015161927613607902831542857977859612596282353679327773303727004407262197231586324599181983572622404590354084541788062262164510140605868122410388090174420147752408554129789760902300898046273909007852818474030770699647647363015102118956737673941354217692696044969695308506436573142565573487583507037356944848039864382339216266670673567488871508925311154801
e1=11187289
c2=18702010045187015556548691642394982835669262147230212731309938675226458555210425972429418449273410535387985931036711854265623905066805665751803269106880746769003478900791099590239513925449748814075904017471585572848473556490565450062664706449128415834787961947266259789785962922238701134079720414228414066193071495304612341052987455615930023536823801499269773357186087452747500840640419365011554421183037505653461286732740983702740822671148045619497667184586123657285604061875653909567822328914065337797733444640351518775487649819978262363617265797982843179630888729407238496650987720428708217115257989007867331698397
e2=9647291

题解

共模攻击

上代码

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
import gmpy2
import libnum

c1=22322035275663237041646893770451933509324701913484303338076210603542612758956262869640822486470121149424485571361007421293675516338822195280313794991136048140918842471219840263536338886250492682739436410013436651161720725855484866690084788721349555662019879081501113222996123305533009325964377798892703161521852805956811219563883312896330156298621674684353919547558127920925706842808914762199011054955816534977675267395009575347820387073483928425066536361482774892370969520740304287456555508933372782327506569010772537497541764311429052216291198932092617792645253901478910801592878203564861118912045464959832566051361
n=22708078815885011462462049064339185898712439277226831073457888403129378547350292420267016551819052430779004755846649044001024141485283286483130702616057274698473611149508798869706347501931583117632710700787228016480127677393649929530416598686027354216422565934459015161927613607902831542857977859612596282353679327773303727004407262197231586324599181983572622404590354084541788062262164510140605868122410388090174420147752408554129789760902300898046273909007852818474030770699647647363015102118956737673941354217692696044969695308506436573142565573487583507037356944848039864382339216266670673567488871508925311154801
e1=11187289
c2=18702010045187015556548691642394982835669262147230212731309938675226458555210425972429418449273410535387985931036711854265623905066805665751803269106880746769003478900791099590239513925449748814075904017471585572848473556490565450062664706449128415834787961947266259789785962922238701134079720414228414066193071495304612341052987455615930023536823801499269773357186087452747500840640419365011554421183037505653461286732740983702740822671148045619497667184586123657285604061875653909567822328914065337797733444640351518775487649819978262363617265797982843179630888729407238496650987720428708217115257989007867331698397
e2=9647291

s, s1, s2 = gmpy2.gcdext(e1, e2)  # s为gcd(e1, e2)
m = int(pow(c1, s1, n) * pow(c2, s2, n) % n)
print(libnum.n2s(m))

RSA2

题目

1
2
3
4
5
e = 65537
n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657

c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751

题解

dp泄漏

代码

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

e = 65537
n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751
dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657


for a in range(1, e+1):
    if (dp*e-1) % a == 0:
        if n % ((dp*e-1) // a + 1) == 0:  # ! 关键，易错
            p = (dp*e-1) // a + 1
            q = n // p
            phi = (p - 1) * (q - 1)
            d = gp.invert(e, phi)
            m = pow(c, d, n)
            print(long_to_bytes(m))
            break
    else:
        a += 1

RSAROLL

题目

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
38
39
40
41
42
43
44
45
46
47
# 题目.txt
RSA roll！roll！roll！
Only number and a-z
（don't use editor
which MS provide）

# data.txt
{920139713,19}

704796792
752211152
274704164
18414022
368270835
483295235
263072905
459788476
483295235
459788476
663551792
475206804
459788476
428313374
475206804
459788476
425392137
704796792
458265677
341524652
483295235
534149509
425392137
428313374
425392137
341524652
458265677
263072905
483295235
828509797
341524652
425392137
475206804
428313374
483295235
475206804
459788476
306220148

题解

不知道题目的考点在哪，无从下手。

学习他人题解后，得知：

  • {920139713,19}

    n = 920139713,

    e = 19

  • 分解 n得到：

    q = 18443

    p = 49891

  • 常规求phi、d后，对每一行密文（c）进行解密

代码

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
38
39
40
41
42
43
44
45
46
47
48
49
import gmpy2
n = 920139713
q = 18443
p = 49891
e = 19
d = int(gmpy2.invert(e , (p-1) * (q-1)))

c = '''704796792
752211152
274704164
18414022
368270835
483295235
263072905
459788476
483295235
459788476
663551792
475206804
459788476
428313374
475206804
459788476
425392137
704796792
458265677
341524652
483295235
534149509
425392137
428313374
425392137
341524652
458265677
263072905
483295235
828509797
341524652
425392137
475206804
428313374
483295235
475206804
459788476
306220148'''
flag = ''
for ii in c.split('\n'):
	flag += chr(pow(int(ii),d,n))
print(flag)

rsa2

题目

1
2
3
4
5
6
7
import hashlib
import gmpy2

N = 101991809777553253470276751399264740131157682329252673501792154507006158434432009141995367241962525705950046253400188884658262496534706438791515071885860897552736656899566915731297225817250639873643376310103992170646906557242832893914902053581087502512787303322747780420210884852166586717636559058152544979471
e = 46731919563265721307105180410302518676676135509737992912625092976849075262192092549323082367518264378630543338219025744820916471913696072050291990620486581719410354385121760761374229374847695148230596005409978383369740305816082770283909611956355972181848077519920922059268376958811713365106925235218265173085

flag = "flag{" + hashlib.md5(hex(d).encode()).hexdigest() + "}"

题解

看出来求d再md5转换后即可。

但此题的p、q发现可拆，则有以下

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import hashlib
import gmpy2

N = 101991809777553253470276751399264740131157682329252673501792154507006158434432009141995367241962525705950046253400188884658262496534706438791515071885860897552736656899566915731297225817250639873643376310103992170646906557242832893914902053581087502512787303322747780420210884852166586717636559058152544979471
e = 46731919563265721307105180410302518676676135509737992912625092976849075262192092549323082367518264378630543338219025744820916471913696072050291990620486581719410354385121760761374229374847695148230596005409978383369740305816082770283909611956355972181848077519920922059268376958811713365106925235218265173085
p = 9046853915223503351787031888977627106934564043204783593118678181991596316582877057556463152579621699010610569526573031954779520781448550677767565207407183
q = 11273732364123571293429600400343309403733952146912318879993851141423284675797325272321856863528776914709992821287788339848962916204774010644058033316303937
phi = (p - 1) * (q - 1)
d = gmpy2.invert(e, phi)
print(d)
# 8920758995414587152829426558580025657357328745839747693739591820283538307445

flag = "flag{" + hashlib.md5(hex(int(d)).encode()).hexdigest() + "}"
print(flag)
# flag{8159e6c4abdd3b94ce461ed9a1a24017}   ❌     Py3
# flag{2cf5122fc7b4e0e24c93d8c2f8323b10}   ❌     CMD5 
# flag{47bf28da384590448e0b0d23909a25a4}   ✅     Py2

交了好几次flag都错了，对比他人题解，得知：

  • d没错，此方法可行

  • 因为Py2与Py3的差异，导致相同值的md5值不同

    Python·md5注意事项

  • 其后在cmd5网站加密后的结果与另一部分题解相同，但仍不正确

  • 必须在Py2环境下md5加密

总结

Python2.X的环境还得留着，以备不时之需

RSA5

题目

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
m = xxxxxxxx
e = 65537
========== n c ==========
n = 20474918894051778533305262345601880928088284471121823754049725354072477155873778848055073843345820697886641086842612486541250183965966001591342031562953561793332341641334302847996108417466360688139866505179689516589305636902137210185624650854906780037204412206309949199080005576922775773722438863762117750429327585792093447423980002401200613302943834212820909269713876683465817369158585822294675056978970612202885426436071950214538262921077409076160417436699836138801162621314845608796870206834704116707763169847387223307828908570944984416973019427529790029089766264949078038669523465243837675263858062854739083634207
c = 974463908243330865728978769213595400782053398596897741316275722596415018912929508637393850919224969271766388710025195039896961956062895570062146947736340342927974992616678893372744261954172873490878805483241196345881721164078651156067119957816422768524442025688079462656755605982104174001635345874022133045402344010045961111720151990412034477755851802769069309069018738541854130183692204758761427121279982002993939745343695671900015296790637464880337375511536424796890996526681200633086841036320395847725935744757993013352804650575068136129295591306569213300156333650910795946800820067494143364885842896291126137320

n = 20918819960648891349438263046954902210959146407860980742165930253781318759285692492511475263234242002509419079545644051755251311392635763412553499744506421566074721268822337321637265942226790343839856182100575539845358877493718334237585821263388181126545189723429262149630651289446553402190531135520836104217160268349688525168375213462570213612845898989694324269410202496871688649978370284661017399056903931840656757330859626183773396574056413017367606446540199973155630466239453637232936904063706551160650295031273385619470740593510267285957905801566362502262757750629162937373721291789527659531499435235261620309759
c = 15819636201971185538694880505120469332582151856714070824521803121848292387556864177196229718923770810072104155432038682511434979353089791861087415144087855679134383396897817458726543883093567600325204596156649305930352575274039425470836355002691145864435755333821133969266951545158052745938252574301327696822347115053614052423028835532509220641378760800693351542633860702225772638930501021571415907348128269681224178300248272689705308911282208685459668200507057183420662959113956077584781737983254788703048275698921427029884282557468334399677849962342196140864403989162117738206246183665814938783122909930082802031855

n = 25033254625906757272369609119214202033162128625171246436639570615263949157363273213121556825878737923265290579551873824374870957467163989542063489416636713654642486717219231225074115269684119428086352535471683359486248203644461465935500517901513233739152882943010177276545128308412934555830087776128355125932914846459470221102007666912211992310538890654396487111705385730502843589727289829692152177134753098649781412247065660637826282055169991824099110916576856188876975621376606634258927784025787142263367152947108720757222446686415627479703666031871635656314282727051189190889008763055811680040315277078928068816491
c = 4185308529416874005831230781014092407198451385955677399668501833902623478395669279404883990725184332709152443372583701076198786635291739356770857286702107156730020004358955622511061410661058982622055199736820808203841446796305284394651714430918690389486920560834672316158146453183789412140939029029324756035358081754426645160033262924330248675216108270980157049705488620263485129480952814764002865280019185127662449318324279383277766416258142275143923532168798413011028271543085249029048997452212503111742302302065401051458066585395360468447460658672952851643547193822775218387853623453638025492389122204507555908862

n = 21206968097314131007183427944486801953583151151443627943113736996776787181111063957960698092696800555044199156765677935373149598221184792286812213294617749834607696302116136745662816658117055427803315230042700695125718401646810484873064775005221089174056824724922160855810527236751389605017579545235876864998419873065217294820244730785120525126565815560229001887622837549118168081685183371092395128598125004730268910276024806808565802081366898904032509920453785997056150497645234925528883879419642189109649009132381586673390027614766605038951015853086721168018787523459264932165046816881682774229243688581614306480751
c = 4521038011044758441891128468467233088493885750850588985708519911154778090597136126150289041893454126674468141393472662337350361712212694867311622970440707727941113263832357173141775855227973742571088974593476302084111770625764222838366277559560887042948859892138551472680654517814916609279748365580610712259856677740518477086531592233107175470068291903607505799432931989663707477017904611426213770238397005743730386080031955694158466558475599751940245039167629126576784024482348452868313417471542956778285567779435940267140679906686531862467627238401003459101637191297209422470388121802536569761414457618258343550613

n = 22822039733049388110936778173014765663663303811791283234361230649775805923902173438553927805407463106104699773994158375704033093471761387799852168337898526980521753614307899669015931387819927421875316304591521901592823814417756447695701045846773508629371397013053684553042185725059996791532391626429712416994990889693732805181947970071429309599614973772736556299404246424791660679253884940021728846906344198854779191951739719342908761330661910477119933428550774242910420952496929605686154799487839923424336353747442153571678064520763149793294360787821751703543288696726923909670396821551053048035619499706391118145067
c = 15406498580761780108625891878008526815145372096234083936681442225155097299264808624358826686906535594853622687379268969468433072388149786607395396424104318820879443743112358706546753935215756078345959375299650718555759698887852318017597503074317356745122514481807843745626429797861463012940172797612589031686718185390345389295851075279278516147076602270178540690147808314172798987497259330037810328523464851895621851859027823681655934104713689539848047163088666896473665500158179046196538210778897730209572708430067658411755959866033531700460551556380993982706171848970460224304996455600503982223448904878212849412357

n = 21574139855341432908474064784318462018475296809327285532337706940126942575349507668289214078026102682252713757703081553093108823214063791518482289846780197329821139507974763780260290309600884920811959842925540583967085670848765317877441480914852329276375776405689784571404635852204097622600656222714808541872252335877037561388406257181715278766652824786376262249274960467193961956690974853679795249158751078422296580367506219719738762159965958877806187461070689071290948181949561254144310776943334859775121650186245846031720507944987838489723127897223416802436021278671237227993686791944711422345000479751187704426369
c = 20366856150710305124583065375297661819795242238376485264951185336996083744604593418983336285185491197426018595031444652123288461491879021096028203694136683203441692987069563513026001861435722117985559909692670907347563594578265880806540396777223906955491026286843168637367593400342814725694366078337030937104035993569672959361347287894143027186846856772983058328919716702982222142848848117768499996617588305301483085428547267337070998767412540225911508196842253134355901263861121500650240296746702967594224401650220168780537141654489215019142122284308116284129004257364769474080721001708734051264841350424152506027932

n = 25360227412666612490102161131174584819240931803196448481224305250583841439581008528535930814167338381983764991296575637231916547647970573758269411168219302370541684789125112505021148506809643081950237623703181025696585998044695691322012183660424636496897073045557400768745943787342548267386564625462143150176113656264450210023925571945961405709276631990731602198104287528528055650050486159837612279600415259486306154947514005408907590083747758953115486124865486720633820559135063440942528031402951958557630833503775112010715604278114325528993771081233535247118481765852273252404963430792898948219539473312462979849137
c = 19892772524651452341027595619482734356243435671592398172680379981502759695784087900669089919987705675899945658648623800090272599154590123082189645021800958076861518397325439521139995652026377132368232502108620033400051346127757698623886142621793423225749240286511666556091787851683978017506983310073524398287279737680091787333547538239920607761080988243639547570818363788673249582783015475682109984715293163137324439862838574460108793714172603672477766831356411304446881998674779501188163600664488032943639694828698984739492200699684462748922883550002652913518229322945040819064133350314536378694523704793396169065179

n = 22726855244632356029159691753451822163331519237547639938779517751496498713174588935566576167329576494790219360727877166074136496129927296296996970048082870488804456564986667129388136556137013346228118981936899510687589585286517151323048293150257036847475424044378109168179412287889340596394755257704938006162677656581509375471102546261355748251869048003600520034656264521931808651038524134185732929570384705918563982065684145766427962502261522481994191989820110575981906998431553107525542001187655703534683231777988419268338249547641335718393312295800044734534761692799403469497954062897856299031257454735945867491191
c = 6040119795175856407541082360023532204614723858688636724822712717572759793960246341800308149739809871234313049629732934797569781053000686185666374833978403290525072598774001731350244744590772795701065129561898116576499984185920661271123665356132719193665474235596884239108030605882777868856122378222681140570519180321286976947154042272622411303981011302586225630859892731724640574658125478287115198406253847367979883768000812605395482952698689604477719478947595442185921480652637868335673233200662100621025061500895729605305665864693122952557361871523165300206070325660353095592778037767395360329231331322823610060006

n = 23297333791443053297363000786835336095252290818461950054542658327484507406594632785712767459958917943095522594228205423428207345128899745800927319147257669773812669542782839237744305180098276578841929496345963997512244219376701787616046235397139381894837435562662591060768476997333538748065294033141610502252325292801816812268934171361934399951548627267791401089703937389012586581080223313060159456238857080740699528666411303029934807011214953984169785844714159627792016926490955282697877141614638806397689306795328344778478692084754216753425842557818899467945102646776342655167655384224860504086083147841252232760941
c = 5418120301208378713115889465579964257871814114515046096090960159737859076829258516920361577853903925954198406843757303687557848302302200229295916902430205737843601806700738234756698575708612424928480440868739120075888681672062206529156566421276611107802917418993625029690627196813830326369874249777619239603300605876865967515719079797115910578653562787899019310139945904958024882417833736304894765433489476234575356755275147256577387022873348906900149634940747104513850154118106991137072643308620284663108283052245750945228995387803432128842152251549292698947407663643895853432650029352092018372834457054271102816934

n = 28873667904715682722987234293493200306976947898711255064125115933666968678742598858722431426218914462903521596341771131695619382266194233561677824357379805303885993804266436810606263022097900266975250431575654686915049693091467864820512767070713267708993899899011156106766178906700336111712803362113039613548672937053397875663144794018087017731949087794894903737682383916173267421403408140967713071026001874733487295007501068871044649170615709891451856792232315526696220161842742664778581287321318748202431466508948902745314372299799561625186955234673012098210919745879882268512656931714326782335211089576897310591491
c = 9919880463786836684987957979091527477471444996392375244075527841865509160181666543016317634963512437510324198702416322841377489417029572388474450075801462996825244657530286107428186354172836716502817609070590929769261932324275353289939302536440310628698349244872064005700644520223727670950787924296004296883032978941200883362653993351638545860207179022472492671256630427228461852668118035317021428675954874947015197745916918197725121122236369382741533983023462255913924692806249387449016629865823316402366017657844166919846683497851842388058283856219900535567427103603869955066193425501385255322097901531402103883869

n = 22324685947539653722499932469409607533065419157347813961958075689047690465266404384199483683908594787312445528159635527833904475801890381455653807265501217328757871352731293000303438205315816792663917579066674842307743845261771032363928568844669895768092515658328756229245837025261744260614860746997931503548788509983868038349720225305730985576293675269073709022350700836510054067641753713212999954307022524495885583361707378513742162566339010134354907863733205921845038918224463903789841881400814074587261720283879760122070901466517118265422863420376921536734845502100251460872499122236686832189549698020737176683019
c = 1491527050203294989882829248560395184804977277747126143103957219164624187528441047837351263580440686474767380464005540264627910126483129930668344095814547592115061057843470131498075060420395111008619027199037019925701236660166563068245683975787762804359520164701691690916482591026138582705558246869496162759780878437137960823000043988227303003876410503121370163303711603359430764539337597866862508451528158285103251810058741879687875218384160282506172706613359477657215420734816049393339593755489218588796607060261897905233453268671411610631047340459487937479511933450369462213795738933019001471803157607791738538467

n = 27646746423759020111007828653264027999257847645666129907789026054594393648800236117046769112762641778865620892443423100189619327585811384883515424918752749559627553637785037359639801125213256163008431942593727931931898199727552768626775618479833029101249692573716030706695702510982283555740851047022672485743432464647772882314215176114732257497240284164016914018689044557218920300262234652840632406067273375269301008409860193180822366735877288205783314326102263756503786736122321348320031950012144905869556204017430593656052867939493633163499580242224763404338807022510136217187779084917996171602737036564991036724299
c = 21991524128957260536043771284854920393105808126700128222125856775506885721971193109361315961129190814674647136464887087893990660894961612838205086401018885457667488911898654270235561980111174603323721280911197488286585269356849579263043456316319476495888696219344219866516861187654180509247881251251278919346267129904739277386289240394384575124331135655943513831009934023397457082184699737734388823763306805326430395849935770213817533387235486307008892410920611669932693018165569417445885810825749609388627231235840912644654685819620931663346297596334834498661789016450371769203650109994771872404185770230172934013971

n = 20545487405816928731738988374475012686827933709789784391855706835136270270933401203019329136937650878386117187776530639342572123237188053978622697282521473917978282830432161153221216194169879669541998840691383025487220850872075436064308499924958517979727954402965612196081404341651517326364041519250125036424822634354268773895465698920883439222996581226358595873993976604699830613932320720554130011671297944433515047180565484495191003887599891289037982010216357831078328159028953222056918189365840711588671093333013117454034313622855082795813122338562446223041211192277089225078324682108033843023903550172891959673551
c = 14227439188191029461250476692790539654619199888487319429114414557975376308688908028140817157205579804059783807641305577385724758530138514972962209062230576107406142402603484375626077345190883094097636019771377866339531511965136650567412363889183159616188449263752475328663245311059988337996047359263288837436305588848044572937759424466586870280512424336807064729894515840552404756879590698797046333336445465120445087587621743906624279621779634772378802959109714400516183718323267273824736540168545946444437586299214110424738159957388350785999348535171553569373088251552712391288365295267665691357719616011613628772175

n = 27359727711584277234897157724055852794019216845229798938655814269460046384353568138598567755392559653460949444557879120040796798142218939251844762461270251672399546774067275348291003962551964648742053215424620256999345448398805278592777049668281558312871773979931343097806878701114056030041506690476954254006592555275342579529625231194321357904668512121539514880704046969974898412095675082585315458267591016734924646294357666924293908418345508902112711075232047998775303603175363964055048589769318562104883659754974955561725694779754279606726358588862479198815999276839234952142017210593887371950645418417355912567987
c = 3788529784248255027081674540877016372807848222776887920453488878247137930578296797437647922494510483767651150492933356093288965943741570268943861987024276610712717409139946409513963043114463933146088430004237747163422802959250296602570649363016151581364006795894226599584708072582696996740518887606785460775851029814280359385763091078902301957226484620428513604630585131511167015763190591225884202772840456563643159507805711004113901417503751181050823638207803533111429510911616160851391754754434764819568054850823810901159821297849790005646102129354035735350124476838786661542089045509656910348676742844957008857457

n = 27545937603751737248785220891735796468973329738076209144079921449967292572349424539010502287564030116831261268197384650511043068738911429169730640135947800885987171539267214611907687570587001933829208655100828045651391618089603288456570334500533178695238407684702251252671579371018651675054368606282524673369983034682330578308769886456335818733827237294570476853673552685361689144261552895758266522393004116017849397346259119221063821663280935820440671825601452417487330105280889520007917979115568067161590058277418371493228631232457972494285014767469893647892888681433965857496916110704944758070268626897045014782837
c = 14069112970608895732417039977542732665796601893762401500878786871680645798754783315693511261740059725171342404186571066972546332813667711135661176659424619936101038903439144294886379322591635766682645179888058617577572409307484708171144488708410543462972008179994594087473935638026612679389759756811490524127195628741262871304427908481214992471182859308828778119005750928935764927967212343526503410515793717201360360437981322576798056276657140363332700714732224848346808963992302409037706094588964170239521193589470070839790404597252990818583717869140229811712295005710540476356743378906642267045723633874011649259842

n = 25746162075697911560263181791216433062574178572424600336856278176112733054431463253903433128232709054141607100891177804285813783247735063753406524678030561284491481221681954564804141454666928657549670266775659862814924386584148785453647316864935942772919140563506305666207816897601862713092809234429096584753263707828899780979223118181009293655563146526792388913462557306433664296966331469906428665127438829399703002867800269947855869262036714256550075520193125987011945192273531732276641728008406855871598678936585324782438668746810516660152018244253008092470066555687277138937298747951929576231036251316270602513451
c = 17344284860275489477491525819922855326792275128719709401292545608122859829827462088390044612234967551682879954301458425842831995513832410355328065562098763660326163262033200347338773439095709944202252494552172589503915965931524326523663289777583152664722241920800537867331030623906674081852296232306336271542832728410803631170229642717524942332390842467035143631504401140727083270732464237443915263865880580308776111219718961746378842924644142127243573824972533819479079381023103585862099063382129757560124074676150622288706094110075567706403442920696472627797607697962873026112240527498308535903232663939028587036724

n = 23288486934117120315036919418588136227028485494137930196323715336208849327833965693894670567217971727921243839129969128783853015760155446770590696037582684845937132790047363216362087277861336964760890214059732779383020349204803205725870225429985939570141508220041286857810048164696707018663758416807708910671477407366098883430811861933014973409390179948577712579749352299440310543689035651465399867908428885541237776143404376333442949397063249223702355051571790555151203866821867908531733788784978667478707672984539512431549558672467752712004519300318999208102076732501412589104904734983789895358753664077486894529499
c = 10738254418114076548071448844964046468141621740603214384986354189105236977071001429271560636428075970459890958274941762528116445171161040040833357876134689749846940052619392750394683504816081193432350669452446113285638982551762586656329109007214019944975816434827768882704630460001209452239162896576191876324662333153835533956600295255158377025198426950944040643235430211011063586032467724329735785947372051759042138171054165854842472990583800899984893232549092766400510300083585513014171220423103452292891496141806956300396540682381668367564569427813092064053993103537635994311143010708814851867239706492577203899024

n = 19591441383958529435598729113936346657001352578357909347657257239777540424811749817783061233235817916560689138344041497732749011519736303038986277394036718790971374656832741054547056417771501234494768509780369075443550907847298246275717420562375114406055733620258777905222169702036494045086017381084272496162770259955811174440490126514747876661317750649488774992348005044389081101686016446219264069971370646319546429782904810063020324704138495608761532563310699753322444871060383693044481932265801505819646998535192083036872551683405766123968487907648980900712118052346174533513978009131757167547595857552370586353973
c = 3834917098887202931981968704659119341624432294759361919553937551053499607440333234018189141970246302299385742548278589896033282894981200353270637127213483172182529890495903425649116755901631101665876301799865612717750360089085179142750664603454193642053016384714515855868368723508922271767190285521137785688075622832924829248362774476456232826885801046969384519549385428259591566716890844604696258783639390854153039329480726205147199247183621535172450825979047132495439603840806501254997167051142427157381799890725323765558803808030109468048682252028720241357478614704610089120810367192414352034177484688502364022887

n = 19254242571588430171308191757871261075358521158624745702744057556054652332495961196795369630484782930292003238730267396462491733557715379956969694238267908985251699834707734400775311452868924330866502429576951934279223234676654749272932769107390976321208605516299532560054081301829440688796904635446986081691156842271268059970762004259219036753174909942343204432795076377432107630203621754552804124408792358220071862369443201584155711893388877350138023238624566616551246804054720492816226651467017802504094070614892556444425915920269485861799532473383304622064493223627552558344088839860178294589481899206318863310603
c = 6790553533991297205804561991225493105312398825187682250780197510784765226429663284220400480563039341938599783346724051076211265663468643826430109013245014035811178295081939958687087477312867720289964506097819762095244479129359998867671811819738196687884696680463458661374310994610760009474264115750204920875527434486437536623589684519411519100170291423367424938566820315486507444202022408003879118465761273916755290898112991525546114191064022991329724370064632569903856189236177894007766690782630247443895358893983735822824243487181851098787271270256780891094405121947631088729917398317652320497765101790132679171889

n = 26809700251171279102974962949184411136459372267620535198421449833298448092580497485301953796619185339316064387798092220298630428207556482805739803420279056191194360049651767412572609187680508073074653291350998253938793269214230457117194434853888765303403385824786231859450351212449404870776320297419712486574804794325602760347306432927281716160368830187944940128907971027838510079519466846176106565164730963988892400240063089397720414921398936399927948235195085202171264728816184532651138221862240969655185596628285814057082448321749567943946273776184657698104465062749244327092588237927996419620170254423837876806659
c = 386213556608434013769864727123879412041991271528990528548507451210692618986652870424632219424601677524265011043146748309774067894985069288067952546139416819404039688454756044862784630882833496090822568580572859029800646671301748901528132153712913301179254879877441322285914544974519727307311002330350534857867516466612474769753577858660075830592891403551867246057397839688329172530177187042229028685862036140779065771061933528137423019407311473581832405899089709251747002788032002094495379614686544672969073249309703482556386024622814731015767810042969813752548617464974915714425595351940266077021672409858645427346

题解

相同m、e， 不同n

很像是广播攻击，但加密指数不低🤔

还是试了下，没成功

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
import binascii, gmpy2
from functools import reduce

import libnum


def CRT(mi, ai):
    assert (reduce(gmpy2.gcd, mi) == 1)
    assert (isinstance(mi, list) and isinstance(ai, list))
    M = reduce(lambda x, y: x * y, mi)
    ai_ti_Mi = [a * (M // m) * gmpy2.invert(M // m, m) for (m, a) in zip(mi, ai)]
    return reduce(lambda x, y: x + y, ai_ti_Mi) % M


e = 65537

# 获得n、c数据
n_list = []
c_list = []
with open("/Users/wenhui/Desktop/1.txt", "r") as f:
    for each in f:
        if each.startswith("n ="):
            n_list.append(int(each[4:].strip('\n')))
        elif each.startswith("c ="):
            c_list.append(int(each[4:].strip('\n')))


m = gmpy2.iroot(CRT(n_list, c_list), e)[0]
print(m)
print(libnum.n2s(int(m)))

思维窃取ing

奥，拆不出来的p、q

且那么正常的e 不该是低加密指数广播攻击 但n真的很多，就该考虑n不互素，找到p

获得思路后，再写代码！

代码

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
import gmpy2
import libnum

e = 65537

# 获得n、c数据
n_list = []
c_list = []
with open("/Users/wenhui/Desktop/1.txt", "r") as f:
    for each in f:
        if each.startswith("n ="):
            n_list.append(int(each[4:].strip('\n')))
        elif each.startswith("c ="):
            c_list.append(int(each[4:].strip('\n')))

s = 0  # 记录x位置
for x in n_list:
    n = s + 1  # 记录被比较项位置
    while n + 1 <= len(n_list):
        if gmpy2.gcd(x, n_list[n]) != 1:
            print("n1:\n", x, "\n n2: \n", n_list[n], "\n p: \n", gmpy2.gcd(x, n_list[n]), "\n\n\n")

            # 一组，正常求解RSA
            n1 = x
            p = gmpy2.gcd(x, n_list[n])
            q = n1 // p
            phi = (p - 1) * (q - 1)
            c = c_list[s]
            d = int(gmpy2.invert(e, phi))
            m = gmpy2.powmod(c, d, n1)
            print(libnum.n2s(int(m)))
        n += 1
    s += 1

总结

不做题就没有记忆点

不互素在无思路时应该多试试。

[NCTF2019]childRSA

题目

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


def getPrime(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, q = [getPrime(2048) for _ in range(2)]
n = p * q
c = pow(m, e, n)

# n = 32849718197337581823002243717057659218502519004386996660885100592872201948834155543125924395614928962750579667346279456710633774501407292473006312537723894221717638059058796679686953564471994009285384798450493756900459225040360430847240975678450171551048783818642467506711424027848778367427338647282428667393241157151675410661015044633282064056800913282016363415202171926089293431012379261585078566301060173689328363696699811123592090204578098276704877408688525618732848817623879899628629300385790344366046641825507767709276622692835393219811283244303899850483748651722336996164724553364097066493953127153066970594638491950199605713033004684970381605908909693802373826516622872100822213645899846325022476318425889580091613323747640467299866189070780620292627043349618839126919699862580579994887507733838561768581933029077488033326056066378869170169389819542928899483936705521710423905128732013121538495096959944889076705471928490092476616709838980562233255542325528398956185421193665359897664110835645928646616337700617883946369110702443135980068553511927115723157704586595844927607636003501038871748639417378062348085980873502535098755568810971926925447913858894180171498580131088992227637341857123607600275137768132347158657063692388249513
# c = 26308018356739853895382240109968894175166731283702927002165268998773708335216338997058314157717147131083296551313334042509806229853341488461087009955203854253313827608275460592785607739091992591431080342664081962030557042784864074533380701014585315663218783130162376176094773010478159362434331787279303302718098735574605469803801873109982473258207444342330633191849040553550708886593340770753064322410889048135425025715982196600650740987076486540674090923181664281515197679745907830107684777248532278645343716263686014941081417914622724906314960249945105011301731247324601620886782967217339340393853616450077105125391982689986178342417223392217085276465471102737594719932347242482670320801063191869471318313514407997326350065187904154229557706351355052446027159972546737213451422978211055778164578782156428466626894026103053360431281644645515155471301826844754338802352846095293421718249819728205538534652212984831283642472071669494851823123552827380737798609829706225744376667082534026874483482483127491533474306552210039386256062116345785870668331513725792053302188276682550672663353937781055621860101624242216671635824311412793495965628876036344731733142759495348248970313655381407241457118743532311394697763283681852908564387282605279108

题解

直接拆n得到p、q

1
2
3
4
5
6
7
8
9
10
11
12
import gmpy2, libnum


n = 32849718197337581823002243717057659218502519004386996660885100592872201948834155543125924395614928962750579667346279456710633774501407292473006312537723894221717638059058796679686953564471994009285384798450493756900459225040360430847240975678450171551048783818642467506711424027848778367427338647282428667393241157151675410661015044633282064056800913282016363415202171926089293431012379261585078566301060173689328363696699811123592090204578098276704877408688525618732848817623879899628629300385790344366046641825507767709276622692835393219811283244303899850483748651722336996164724553364097066493953127153066970594638491950199605713033004684970381605908909693802373826516622872100822213645899846325022476318425889580091613323747640467299866189070780620292627043349618839126919699862580579994887507733838561768581933029077488033326056066378869170169389819542928899483936705521710423905128732013121538495096959944889076705471928490092476616709838980562233255542325528398956185421193665359897664110835645928646616337700617883946369110702443135980068553511927115723157704586595844927607636003501038871748639417378062348085980873502535098755568810971926925447913858894180171498580131088992227637341857123607600275137768132347158657063692388249513
c = 26308018356739853895382240109968894175166731283702927002165268998773708335216338997058314157717147131083296551313334042509806229853341488461087009955203854253313827608275460592785607739091992591431080342664081962030557042784864074533380701014585315663218783130162376176094773010478159362434331787279303302718098735574605469803801873109982473258207444342330633191849040553550708886593340770753064322410889048135425025715982196600650740987076486540674090923181664281515197679745907830107684777248532278645343716263686014941081417914622724906314960249945105011301731247324601620886782967217339340393853616450077105125391982689986178342417223392217085276465471102737594719932347242482670320801063191869471318313514407997326350065187904154229557706351355052446027159972546737213451422978211055778164578782156428466626894026103053360431281644645515155471301826844754338802352846095293421718249819728205538534652212984831283642472071669494851823123552827380737798609829706225744376667082534026874483482483127491533474306552210039386256062116345785870668331513725792053302188276682550672663353937781055621860101624242216671635824311412793495965628876036344731733142759495348248970313655381407241457118743532311394697763283681852908564387282605279108
p = 178449493212694205742332078583256205058672290603652616240227340638730811945224947826121772642204629335108873832781921390308501763661154638696935732709724016546955977529088135995838497476350749621442719690722226913635772410880516639651363626821442456779009699333452616953193799328647446968707045304702547915799734431818800374360377292309248361548868909066895474518333089446581763425755389837072166970684877011663234978631869703859541876049132713490090720408351108387971577438951727337962368478059295446047962510687695047494480605473377173021467764495541590394732685140829152761532035790187269724703444386838656193674253139
q = 184084121540115307597161367011014142898823526027674354555037785878481711602257307508985022577801782788769786800015984410443717799994642236194840684557538917849420967360121509675348296203886340264385224150964642958965438801864306187503790100281099130863977710204660546799128755418521327290719635075221585824217487386227004673527292281536221958961760681032293340099395863194031788435142296085219594866635192464353365034089592414809332183882423461536123972873871477755949082223830049594561329457349537703926325152949582123419049073013144325689632055433283354999265193117288252918515308767016885678802217366700376654365502867
e = 65537
phi = (p-1)*(q-1)
d = int(gmpy2.invert(e, phi))  # d需要转换为整数型
m = pow(c, d, n)
print(libnum.n2s(m))

[HDCTF2019]bbbbbbrsa

题目

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
38
39
# enc
p = 177077389675257695042507998165006460849
n = 37421829509887796274897162249367329400988647145613325367337968063341372726061
c = ==gMzYDNzIjMxUTNyIzNzIjMyYTM4MDM0gTMwEjNzgTM2UTN4cjNwIjN2QzM5ADMwIDNyMTO4UzM2cTM5kDN2MTOyUTO5YDM0czM3MjM

# encode.py
from base64 import b64encode as b32encode
from gmpy2 import invert,gcd,iroot
from Crypto.Util.number import *
from binascii import a2b_hex,b2a_hex
import random

flag = "******************************"

nbit = 128

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

print p
print n

phi = (p-1)*(q-1)

e = random.randint(50000,70000)

while True:
	if gcd(e,phi) == 1:
		break;
	else:
		e -= 1;

c = pow(int(b2a_hex(flag),16),e,n)

print b32encode(str(c))[::-1]

# 2373740699529364991763589324200093466206785561836101840381622237225512234632

题解

  • q: 题目交代了p、n, 所以 q = n \ q 

    1
    2
    3
    4
    p = 177077389675257695042507998165006460849
    n = 37421829509887796274897162249367329400988647145613325367337968063341372726061
    q = n // p
    phi = (p-1)*(q-1)

  • c: 题目所示，先将flag转为16进制，再转10进制；最后在RSA加密后，base32编码再倒序打印

    对此，只需要将c倒序在解码后RSA解密，即可

    1
    2
    3
    import base64

    c = base64.b32decode(c[::-1])

    但，这么写，执行起来会报错,binascii.Error: Non-base32 digit found

    很让人郁闷，以为写法有问题，改了多次，未果

    最后上CyberChef👨‍🍳,看到用的是base64解码😅，所以是题目写错了吧🤔

    （现在看到了from base64 import b64encode as b32encode，啊这

    image-20220113151520874

  • e: RSA解密中唯一的问题在于，不知道e

    因为知道e的范围是五万到七万，手动爆破即可(使用每一个与phi互素的e，看最后解出来是不是乱码)

    需要手动搜索关键词

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    # 爆破e
    e = 50000
    while e < 70000:
        if gcd(e, phi) == 1:
            print(e)
            d = int(gmpy2.invert(e, phi))
            m = pow(c, d, n)
            print(libnum.n2s(m), "\n\n")
            e += 1
            continue
        else:
            e += 1

image-20220113145655280

😅恍然发现，题目最后一行注释里突兀的数字是十进制的c

最后，经过一点点完善

代码

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
import gmpy2, base64, libnum

p = 177077389675257695042507998165006460849
n = 37421829509887796274897162249367329400988647145613325367337968063341372726061
q = n // p
phi = (p - 1) * (q - 1)

# 获取c
# 对 c倒序 再 base64解码
c = "==gMzYDNzIjMxUTNyIzNzIjMyYTM4MDM0gTMwEjNzgTM2UTN4cjNwIjN2QzM5ADMwIDNyMTO4UzM2cTM5kDN2MTOyUTO5YDM0czM3MjM"
c = int(base64.b64decode(c[::-1]))

# 爆破e，进行RSA解，手动筛选关键词
e = 50000
while e < 70000:
    if gcd(e, phi) == 1:
        d = int(gmpy2.invert(e, phi))
        m = pow(c, d, n)
        flag = libnum.n2s(m)
        if ("flag" or "ctf") in str(flag).lower():
            print(flag.decode())
        e += 1
        continue
    else:
        e += 1

[BJDCTF2020]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
from Crypto.Util.number import getPrime,bytes_to_long

flag=open("flag","rb").read()

p=getPrime(1024)
q=getPrime(1024)
assert(e<100000)
n=p*q
m=bytes_to_long(flag)
c=pow(m,e,n)
print c,n
print pow(294,e,n)

p=getPrime(1024)
n=p*q
m=bytes_to_long("BJD"*32)
c=pow(m,e,n)
print c,n

'''
output:
12641635617803746150332232646354596292707861480200207537199141183624438303757120570096741248020236666965755798009656547738616399025300123043766255518596149348930444599820675230046423373053051631932557230849083426859490183732303751744004874183062594856870318614289991675980063548316499486908923209627563871554875612702079100567018698992935818206109087568166097392314105717555482926141030505639571708876213167112187962584484065321545727594135175369233925922507794999607323536976824183162923385005669930403448853465141405846835919842908469787547341752365471892495204307644586161393228776042015534147913888338316244169120  13508774104460209743306714034546704137247627344981133461801953479736017021401725818808462898375994767375627749494839671944543822403059978073813122441407612530658168942987820256786583006947001711749230193542370570950705530167921702835627122401475251039000775017381633900222474727396823708695063136246115652622259769634591309421761269548260984426148824641285010730983215377509255011298737827621611158032976420011662547854515610597955628898073569684158225678333474543920326532893446849808112837476684390030976472053905069855522297850688026960701186543428139843783907624317274796926248829543413464754127208843070331063037
381631268825806469518166370387352035475775677163615730759454343913563615970881967332407709901235637718936184198930226303761876517101208677107311006065728014220477966000620964056616058676999878976943319063836649085085377577273214792371548775204594097887078898598463892440141577974544939268247818937936607013100808169758675042264568547764031628431414727922168580998494695800403043312406643527637667466318473669542326169218665366423043579003388486634167642663495896607282155808331902351188500197960905672207046579647052764579411814305689137519860880916467272056778641442758940135016400808740387144508156358067955215018
979153370552535153498477459720877329811204688208387543826122582132404214848454954722487086658061408795223805022202997613522014736983452121073860054851302343517756732701026667062765906277626879215457936330799698812755973057557620930172778859116538571207100424990838508255127616637334499680058645411786925302368790414768248611809358160197554369255458675450109457987698749584630551177577492043403656419968285163536823819817573531356497236154342689914525321673807925458651854768512396355389740863270148775362744448115581639629326362342160548500035000156097215446881251055505465713854173913142040976382500435185442521721  12806210903061368369054309575159360374022344774547459345216907128193957592938071815865954073287532545947370671838372144806539753829484356064919357285623305209600680570975224639214396805124350862772159272362778768036844634760917612708721787320159318432456050806227784435091161119982613987303255995543165395426658059462110056431392517548717447898084915167661172362984251201688639469652283452307712821398857016487590794996544468826705600332208535201443322267298747117528882985955375246424812616478327182399461709978893464093245135530135430007842223389360212803439850867615121148050034887767584693608776323252233254261047
'''

题解

常规题目

  • n1、n2不互素

    1
    2
    3
    4
    5
    n1 = 13508774104460209743306714034546704137247627344981133461801953479736017021401725818808462898375994767375627749494839671944543822403059978073813122441407612530658168942987820256786583006947001711749230193542370570950705530167921702835627122401475251039000775017381633900222474727396823708695063136246115652622259769634591309421761269548260984426148824641285010730983215377509255011298737827621611158032976420011662547854515610597955628898073569684158225678333474543920326532893446849808112837476684390030976472053905069855522297850688026960701186543428139843783907624317274796926248829543413464754127208843070331063037
    n2 = 12806210903061368369054309575159360374022344774547459345216907128193957592938071815865954073287532545947370671838372144806539753829484356064919357285623305209600680570975224639214396805124350862772159272362778768036844634760917612708721787320159318432456050806227784435091161119982613987303255995543165395426658059462110056431392517548717447898084915167661172362984251201688639469652283452307712821398857016487590794996544468826705600332208535201443322267298747117528882985955375246424812616478327182399461709978893464093245135530135430007842223389360212803439850867615121148050034887767584693608776323252233254261047
    q = gcd(n1, n2)
    p1 = n1 // q
    p2 = n2 // q

  • 爆破e:因为m2已知，且与m1共用e

    这里注意用加密方式爆破（$c = m^{e} \mod n$)

    1
    2
    3
    4
    for e in range(100000):
        if pow(m2, e, n2) == c2:
            print(e)
            break

代码

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
from Crypto.Util.number import bytes_to_long
import gmpy2

n1 = 13508774104460209743306714034546704137247627344981133461801953479736017021401725818808462898375994767375627749494839671944543822403059978073813122441407612530658168942987820256786583006947001711749230193542370570950705530167921702835627122401475251039000775017381633900222474727396823708695063136246115652622259769634591309421761269548260984426148824641285010730983215377509255011298737827621611158032976420011662547854515610597955628898073569684158225678333474543920326532893446849808112837476684390030976472053905069855522297850688026960701186543428139843783907624317274796926248829543413464754127208843070331063037
n2 = 12806210903061368369054309575159360374022344774547459345216907128193957592938071815865954073287532545947370671838372144806539753829484356064919357285623305209600680570975224639214396805124350862772159272362778768036844634760917612708721787320159318432456050806227784435091161119982613987303255995543165395426658059462110056431392517548717447898084915167661172362984251201688639469652283452307712821398857016487590794996544468826705600332208535201443322267298747117528882985955375246424812616478327182399461709978893464093245135530135430007842223389360212803439850867615121148050034887767584693608776323252233254261047
q = gcd(n1, n2)
p1 = n1 // q
p2 = n2 // q
m2 = "BJD" * 32
m2 = bytes_to_long(m2.encode())
c2 = 979153370552535153498477459720877329811204688208387543826122582132404214848454954722487086658061408795223805022202997613522014736983452121073860054851302343517756732701026667062765906277626879215457936330799698812755973057557620930172778859116538571207100424990838508255127616637334499680058645411786925302368790414768248611809358160197554369255458675450109457987698749584630551177577492043403656419968285163536823819817573531356497236154342689914525321673807925458651854768512396355389740863270148775362744448115581639629326362342160548500035000156097215446881251055505465713854173913142040976382500435185442521721

# 爆破e
"""for e in range(100000):
    if pow(m2, e, n2) == c2:
        print(e)
        # 52361
        break"""

e = 52361
c1 = 12641635617803746150332232646354596292707861480200207537199141183624438303757120570096741248020236666965755798009656547738616399025300123043766255518596149348930444599820675230046423373053051631932557230849083426859490183732303751744004874183062594856870318614289991675980063548316499486908923209627563871554875612702079100567018698992935818206109087568166097392314105717555482926141030505639571708876213167112187962584484065321545727594135175369233925922507794999607323536976824183162923385005669930403448853465141405846835919842908469787547341752365471892495204307644586161393228776042015534147913888338316244169120
phi1 = (p1-1)*(q-1)
d1 = int(gmpy2.invert(e, phi1))
m1 = pow(c1, d1, n1)
print(libnum.n2s(m1))

总结

BUUCTF平台前缀统一为flag,记得改格式。

[BJDCTF2020]rsa_output

题目

1
2
3
4
5
6
7
{21058339337354287847534107544613605305015441090508924094198816691219103399526800112802416383088995253908857460266726925615826895303377801614829364034624475195859997943146305588315939130777450485196290766249612340054354622516207681542973756257677388091926549655162490873849955783768663029138647079874278240867932127196686258800146911620730706734103611833179733264096475286491988063990431085380499075005629807702406676707841324660971173253100956362528346684752959937473852630145893796056675793646430793578265418255919376323796044588559726703858429311784705245069845938316802681575653653770883615525735690306674635167111,2767}

{21058339337354287847534107544613605305015441090508924094198816691219103399526800112802416383088995253908857460266726925615826895303377801614829364034624475195859997943146305588315939130777450485196290766249612340054354622516207681542973756257677388091926549655162490873849955783768663029138647079874278240867932127196686258800146911620730706734103611833179733264096475286491988063990431085380499075005629807702406676707841324660971173253100956362528346684752959937473852630145893796056675793646430793578265418255919376323796044588559726703858429311784705245069845938316802681575653653770883615525735690306674635167111,3659}

message1=20152490165522401747723193966902181151098731763998057421967155300933719378216342043730801302534978403741086887969040721959533190058342762057359432663717825826365444996915469039056428416166173920958243044831404924113442512617599426876141184212121677500371236937127571802891321706587610393639446868836987170301813018218408886968263882123084155607494076330256934285171370758586535415136162861138898728910585138378884530819857478609791126971308624318454905992919405355751492789110009313138417265126117273710813843923143381276204802515910527468883224274829962479636527422350190210717694762908096944600267033351813929448599

message2=11298697323140988812057735324285908480504721454145796535014418738959035245600679947297874517818928181509081545027056523790022598233918011261011973196386395689371526774785582326121959186195586069851592467637819366624044133661016373360885158956955263645614345881350494012328275215821306955212788282617812686548883151066866149060363482958708364726982908798340182288702101023393839781427386537230459436512613047311585875068008210818996941460156589314135010438362447522428206884944952639826677247819066812706835773107059567082822312300721049827013660418610265189288840247186598145741724084351633508492707755206886202876227

题解

  • 翻译一下题目

    1
    2
    3
    4
    5
    n = 21058339337354287847534107544613605305015441090508924094198816691219103399526800112802416383088995253908857460266726925615826895303377801614829364034624475195859997943146305588315939130777450485196290766249612340054354622516207681542973756257677388091926549655162490873849955783768663029138647079874278240867932127196686258800146911620730706734103611833179733264096475286491988063990431085380499075005629807702406676707841324660971173253100956362528346684752959937473852630145893796056675793646430793578265418255919376323796044588559726703858429311784705245069845938316802681575653653770883615525735690306674635167111
    e1 = 2767
    e2 = 3659
    c1 = 20152490165522401747723193966902181151098731763998057421967155300933719378216342043730801302534978403741086887969040721959533190058342762057359432663717825826365444996915469039056428416166173920958243044831404924113442512617599426876141184212121677500371236937127571802891321706587610393639446868836987170301813018218408886968263882123084155607494076330256934285171370758586535415136162861138898728910585138378884530819857478609791126971308624318454905992919405355751492789110009313138417265126117273710813843923143381276204802515910527468883224274829962479636527422350190210717694762908096944600267033351813929448599
    c2 = 11298697323140988812057735324285908480504721454145796535014418738959035245600679947297874517818928181509081545027056523790022598233918011261011973196386395689371526774785582326121959186195586069851592467637819366624044133661016373360885158956955263645614345881350494012328275215821306955212788282617812686548883151066866149060363482958708364726982908798340182288702101023393839781427386537230459436512613047311585875068008210818996941460156589314135010438362447522428206884944952639826677247819066812706835773107059567082822312300721049827013660418610265189288840247186598145741724084351633508492707755206886202876227

  • 不难发现，考查共模攻击

代码

1
2
3
4
5
6
7
8
9
10
11
12
import gmpy2
import libnum

c1 = 20152490165522401747723193966902181151098731763998057421967155300933719378216342043730801302534978403741086887969040721959533190058342762057359432663717825826365444996915469039056428416166173920958243044831404924113442512617599426876141184212121677500371236937127571802891321706587610393639446868836987170301813018218408886968263882123084155607494076330256934285171370758586535415136162861138898728910585138378884530819857478609791126971308624318454905992919405355751492789110009313138417265126117273710813843923143381276204802515910527468883224274829962479636527422350190210717694762908096944600267033351813929448599
n = 21058339337354287847534107544613605305015441090508924094198816691219103399526800112802416383088995253908857460266726925615826895303377801614829364034624475195859997943146305588315939130777450485196290766249612340054354622516207681542973756257677388091926549655162490873849955783768663029138647079874278240867932127196686258800146911620730706734103611833179733264096475286491988063990431085380499075005629807702406676707841324660971173253100956362528346684752959937473852630145893796056675793646430793578265418255919376323796044588559726703858429311784705245069845938316802681575653653770883615525735690306674635167111
e1 = 2767
c2 = 11298697323140988812057735324285908480504721454145796535014418738959035245600679947297874517818928181509081545027056523790022598233918011261011973196386395689371526774785582326121959186195586069851592467637819366624044133661016373360885158956955263645614345881350494012328275215821306955212788282617812686548883151066866149060363482958708364726982908798340182288702101023393839781427386537230459436512613047311585875068008210818996941460156589314135010438362447522428206884944952639826677247819066812706835773107059567082822312300721049827013660418610265189288840247186598145741724084351633508492707755206886202876227
e2 = 3659

s, s1, s2 = gmpy2.gcdext(e1, e2)  # s为gcd(e1, e2)
m = int(pow(c1, s1, n) * pow(c2, s2, n) % n)
print(libnum.n2s(m))

RSA4

题目

1
2
3
4
5
6
7
8
N = 331310324212000030020214312244232222400142410423413104441140203003243002104333214202031202212403400220031202142322434104143104244241214204444443323000244130122022422310201104411044030113302323014101331214303223312402430402404413033243132101010422240133122211400434023222214231402403403200012221023341333340042343122302113410210110221233241303024431330001303404020104442443120130000334110042432010203401440404010003442001223042211442001413004 
c = 310020004234033304244200421414413320341301002123030311202340222410301423440312412440240244110200112141140201224032402232131204213012303204422003300004011434102141321223311243242010014140422411342304322201241112402132203101131221223004022003120002110230023341143201404311340311134230140231412201333333142402423134333211302102413111111424430032440123340034044314223400401224111323000242234420441240411021023100222003123214343030122032301042243

N = 302240000040421410144422133334143140011011044322223144412002220243001141141114123223331331304421113021231204322233120121444434210041232214144413244434424302311222143224402302432102242132244032010020113224011121043232143221203424243134044314022212024343100042342002432331144300214212414033414120004344211330224020301223033334324244031204240122301242232011303211220044222411134403012132420311110302442344021122101224411230002203344140143044114 
c = 112200203404013430330214124004404423210041321043000303233141423344144222343401042200334033203124030011440014210112103234440312134032123400444344144233020130110134042102220302002413321102022414130443041144240310121020100310104334204234412411424420321211112232031121330310333414423433343322024400121200333330432223421433344122023012440013041401423202210124024431040013414313121123433424113113414422043330422002314144111134142044333404112240344

N = 332200324410041111434222123043121331442103233332422341041340412034230003314420311333101344231212130200312041044324431141033004333110021013020140020011222012300020041342040004002220210223122111314112124333211132230332124022423141214031303144444134403024420111423244424030030003340213032121303213343020401304243330001314023030121034113334404440421242240113103203013341231330004332040302440011324004130324034323430143102401440130242321424020323 
c = 10013444120141130322433204124002242224332334011124210012440241402342100410331131441303242011002101323040403311120421304422222200324402244243322422444414043342130111111330022213203030324422101133032212042042243101434342203204121042113212104212423330331134311311114143200011240002111312122234340003403312040401043021433112031334324322123304112340014030132021432101130211241134422413442312013042141212003102211300321404043012124332013240431242

题解

校内CTF平台同款的密码题

当时折磨了我一两周 ： ）

  • 五进制：N、c数字很有特点，各位数都不超过5

  • 低加密指数广播攻击：

    • 判断在于许多N、c；
    • 未给e(尝试e=3

代码

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
import gmpy2
from functools import reduce
import libnum


def CRT(mi, ai):
    assert(reduce(gmpy2.gcd,mi)==1)
    assert (isinstance(mi, list) and isinstance(ai, list))
    M = reduce(lambda x, y: x * y, mi)
    ai_ti_Mi = [a * (M // m) * gmpy2.invert(M // m, m) for (m, a) in zip(mi, ai)]
    return reduce(lambda x, y: x + y, ai_ti_Mi) % M

e= 3
n= [331310324212000030020214312244232222400142410423413104441140203003243002104333214202031202212403400220031202142322434104143104244241214204444443323000244130122022422310201104411044030113302323014101331214303223312402430402404413033243132101010422240133122211400434023222214231402403403200012221023341333340042343122302113410210110221233241303024431330001303404020104442443120130000334110042432010203401440404010003442001223042211442001413004, 302240000040421410144422133334143140011011044322223144412002220243001141141114123223331331304421113021231204322233120121444434210041232214144413244434424302311222143224402302432102242132244032010020113224011121043232143221203424243134044314022212024343100042342002432331144300214212414033414120004344211330224020301223033334324244031204240122301242232011303211220044222411134403012132420311110302442344021122101224411230002203344140143044114, 332200324410041111434222123043121331442103233332422341041340412034230003314420311333101344231212130200312041044324431141033004333110021013020140020011222012300020041342040004002220210223122111314112124333211132230332124022423141214031303144444134403024420111423244424030030003340213032121303213343020401304243330001314023030121034113334404440421242240113103203013341231330004332040302440011324004130324034323430143102401440130242321424020323]
c= [310020004234033304244200421414413320341301002123030311202340222410301423440312412440240244110200112141140201224032402232131204213012303204422003300004011434102141321223311243242010014140422411342304322201241112402132203101131221223004022003120002110230023341143201404311340311134230140231412201333333142402423134333211302102413111111424430032440123340034044314223400401224111323000242234420441240411021023100222003123214343030122032301042243, 112200203404013430330214124004404423210041321043000303233141423344144222343401042200334033203124030011440014210112103234440312134032123400444344144233020130110134042102220302002413321102022414130443041144240310121020100310104334204234412411424420321211112232031121330310333414423433343322024400121200333330432223421433344122023012440013041401423202210124024431040013414313121123433424113113414422043330422002314144111134142044333404112240344, 10013444120141130322433204124002242224332334011124210012440241402342100410331131441303242011002101323040403311120421304422222200324402244243322422444414043342130111111330022213203030324422101133032212042042243101434342203204121042113212104212423330331134311311114143200011240002111312122234340003403312040401043021433112031334324322123304112340014030132021432101130211241134422413442312013042141212003102211300321404043012124332013240431242]

#  五进制转十进制
n1 = []
c1 = []
for each in n:
    n1.append(int(str(each), 5))
for each in c:
    c1.append(int(str(each), 5))
n = n1
c = c1

# 利用中国剩余定理求解
m = gmpy2.iroot(CRT(n, c), e)[0]
print(libnum.n2s(int(m)).decode())

总结

  • 学会对现有题型的利用，识别新题目中的老考点
  • 猜测中，e往往不是65537就很可能是3

[WUSTCTF2020]babyrsa

题目

1
2
3
c = 28767758880940662779934612526152562406674613203406706867456395986985664083182
n = 73069886771625642807435783661014062604264768481735145873508846925735521695159
e = 65537

题解

没什么特殊的常规题。

代码

1
2
3
4
5
6
7
8
9
10
import gmpy2, libnum
c = 28767758880940662779934612526152562406674613203406706867456395986985664083182
n = 73069886771625642807435783661014062604264768481735145873508846925735521695159
e = 65537
p = 189239861511125143212536989589123569301
q = 386123125371923651191219869811293586459
phi = (p-1)*(q-1)
d = int(gmpy2.invert(e, phi))
m = gmpy2.powmod(c, d, n)
print(libnum.n2s(int(m)))

[GWCTF 2019]BabyRSA

题目

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
38
39
40
41
42
43
44
45
secret
N=636585149594574746909030160182690866222909256464847291783000651837227921337237899651287943597773270944384034858925295744880727101606841413640006527614873110651410155893776548737823152943797884729130149758279127430044739254000426610922834573094957082589539445610828279428814524313491262061930512829074466232633130599104490893572093943832740301809630847541592548921200288222432789208650949937638303429456468889100192613859073752923812454212239908948930178355331390933536771065791817643978763045030833712326162883810638120029378337092938662174119747687899484603628344079493556601422498405360731958162719296160584042671057160241284852522913676264596201906163
m1=90009974341452243216986938028371257528604943208941176518717463554774967878152694586469377765296113165659498726012712288670458884373971419842750929287658640266219686646956929872115782173093979742958745121671928568709468526098715927189829600497283118051641107305128852697032053368115181216069626606165503465125725204875578701237789292966211824002761481815276666236869005129138862782476859103086726091860497614883282949955023222414333243193268564781621699870412557822404381213804026685831221430728290755597819259339616650158674713248841654338515199405532003173732520457813901170264713085107077001478083341339002069870585378257051150217511755761491021553239
m2=487443985757405173426628188375657117604235507936967522993257972108872283698305238454465723214226871414276788912058186197039821242912736742824080627680971802511206914394672159240206910735850651999316100014691067295708138639363203596244693995562780286637116394738250774129759021080197323724805414668042318806010652814405078769738548913675466181551005527065309515364950610137206393257148357659666687091662749848560225453826362271704292692847596339533229088038820532086109421158575841077601268713175097874083536249006018948789413238783922845633494023608865256071962856581229890043896939025613600564283391329331452199062858930374565991634191495137939574539546


encrypt.txt
import hashlib
import sympy
from Crypto.Util.number import *

flag = 'GWHT{******}'
secret = '******'

assert(len(flag) == 38)

half = len(flag) / 2

flag1 = flag[:half]
flag2 = flag[half:]

secret_num = getPrime(1024) * bytes_to_long(secret)

p = sympy.nextprime(secret_num)
q = sympy.nextprime(p)

N = p * q

e = 0x10001

F1 = bytes_to_long(flag1)
F2 = bytes_to_long(flag2)

c1 = F1 + F2
c2 = pow(F1, 3) + pow(F2, 3)
assert(c2 < N)

m1 = pow(c1, e, N)
m2 = pow(c2, e, N)

output = open('secret', 'w')
output.write('N=' + str(N) + '\n')
output.write('m1=' + str(m1) + '\n')
output.write('m2=' + str(m2) + '\n')
output.close()

题解

乍一看，有些头大，仔细琢磨，没有绝对难度

首先，理一下题目操作

  • 把flag平分为F1、F2

  • $ c1 = F1 + F2$

    $c2 = F1^{3} + F2^{3}$

  • 其后，一个让人疑惑的操作

    $ m1 = c1^{e} \mod N$

    $ m2 = c2^{e} \mod N$

    • 因为通常，RSA算法算法中，加解密方程为：

      $c = m^{e} \mod n$

      $m = c^{d} \mod n$

      故，这里的操作具有迷惑性。

      但，我们的目标是明确的，就是想办法求出c1、c2，再通c1、c2想办法求出F1、F2

      • 求解c1、c2

      这里，我的想法💡是：

      把 m1 记作 C1, c1 记作 M1;

      把 m2 记作 C2, c2 记作 M2.

      则，有：

      $ C1 = M1^{e} \mod N$

      $ C2 = M2^{e} \mod N$

      这样，就顺眼了，只是常规的求明文m

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      import gmpy2
      n = 636585149594574746909030160182690866222909256464847291783000651837227921337237899651287943597773270944384034858925295744880727101606841413640006527614873110651410155893776548737823152943797884729130149758279127430044739254000426610922834573094957082589539445610828279428814524313491262061930512829074466232633130599104490893572093943832740301809630847541592548921200288222432789208650949937638303429456468889100192613859073752923812454212239908948930178355331390933536771065791817643978763045030833712326162883810638120029378337092938662174119747687899484603628344079493556601422498405360731958162719296160584042671057160241284852522913676264596201906163
      p = 797862863902421984951231350430312260517773269684958456342860983236184129602390919026048496119757187702076499551310794177917920137646835888862706126924088411570997141257159563952725882214181185531209186972351469946269508511312863779123205322378452194261217016552527754513215520329499967108196968833163329724620251096080377747699
      q = n // p
      phi = (p-1)*(q-1)
      e = 65537
      C1=90009974341452243216986938028371257528604943208941176518717463554774967878152694586469377765296113165659498726012712288670458884373971419842750929287658640266219686646956929872115782173093979742958745121671928568709468526098715927189829600497283118051641107305128852697032053368115181216069626606165503465125725204875578701237789292966211824002761481815276666236869005129138862782476859103086726091860497614883282949955023222414333243193268564781621699870412557822404381213804026685831221430728290755597819259339616650158674713248841654338515199405532003173732520457813901170264713085107077001478083341339002069870585378257051150217511755761491021553239
      C2=487443985757405173426628188375657117604235507936967522993257972108872283698305238454465723214226871414276788912058186197039821242912736742824080627680971802511206914394672159240206910735850651999316100014691067295708138639363203596244693995562780286637116394738250774129759021080197323724805414668042318806010652814405078769738548913675466181551005527065309515364950610137206393257148357659666687091662749848560225453826362271704292692847596339533229088038820532086109421158575841077601268713175097874083536249006018948789413238783922845633494023608865256071962856581229890043896939025613600564283391329331452199062858930374565991634191495137939574539546
      d = int(gmpy2.invert(e, phi))
      c1 = M1 = pow(C1, d, n)
      c2 = M2 = pow(C2, d, n)
      # print(M1)
      #  c1 = M1 = F1+F2 = 2732509502629189160482346120094198557857912754
      # print(M2)
      # c2 = M2 = (F1**3 + F2**3) = 5514544075236012543362261483183657422998274674127032311399076783844902086865451355210243586349132992563718009577051164928513093068525554
      • 求解F1、F2

      这里，我们看到，已求出：

      $c1 = F1+F2$ ———-1

      $c2 = F1^{3} + F2^{3}$

      其后通过将c1三次方后减去c2，得到：

      ${c1^{3} - c2\over 3c1} = F1F2$ ———-2

      由式1、2可得F1、F2,所以下面就该解方程

      ![image-20220114095336077](https://s2.loli.net/2022/01/14/Dby7tNfOvmYhJF4.png)

      • 求解二元一次方程

        这里一开始想使用Sage，可惜，没用明白。

        最后学习并使用了sympy

        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        # 一点数学运算
        A = F1F2 = (pow(c1, 3) - c2) // (3*c1)

        # 二元一次方程组
        """
        F1 · F2 = A
        F1 + F2 = c1
        """
        x = Symbol('x')
        y = Symbol('y')
        solved_value = solve([x * y - A, x + y - c1], [x, y])
        # print(solved_value)
        # [(1141553212031156130619789508463772513350070909, 1590956290598033029862556611630426044507841845), (1590956290598033029862556611630426044507841845, 1141553212031156130619789508463772513350070909)]

可见，求出了F1、F2，这里再调试一下先后顺序，即可。

最终，代码如下

代码

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
import gmpy2, libnum
from sympy import *

n = 636585149594574746909030160182690866222909256464847291783000651837227921337237899651287943597773270944384034858925295744880727101606841413640006527614873110651410155893776548737823152943797884729130149758279127430044739254000426610922834573094957082589539445610828279428814524313491262061930512829074466232633130599104490893572093943832740301809630847541592548921200288222432789208650949937638303429456468889100192613859073752923812454212239908948930178355331390933536771065791817643978763045030833712326162883810638120029378337092938662174119747687899484603628344079493556601422498405360731958162719296160584042671057160241284852522913676264596201906163
p = 797862863902421984951231350430312260517773269684958456342860983236184129602390919026048496119757187702076499551310794177917920137646835888862706126924088411570997141257159563952725882214181185531209186972351469946269508511312863779123205322378452194261217016552527754513215520329499967108196968833163329724620251096080377747699
q = n // p
phi = (p-1)*(q-1)
e = 65537
C1=90009974341452243216986938028371257528604943208941176518717463554774967878152694586469377765296113165659498726012712288670458884373971419842750929287658640266219686646956929872115782173093979742958745121671928568709468526098715927189829600497283118051641107305128852697032053368115181216069626606165503465125725204875578701237789292966211824002761481815276666236869005129138862782476859103086726091860497614883282949955023222414333243193268564781621699870412557822404381213804026685831221430728290755597819259339616650158674713248841654338515199405532003173732520457813901170264713085107077001478083341339002069870585378257051150217511755761491021553239
C2=487443985757405173426628188375657117604235507936967522993257972108872283698305238454465723214226871414276788912058186197039821242912736742824080627680971802511206914394672159240206910735850651999316100014691067295708138639363203596244693995562780286637116394738250774129759021080197323724805414668042318806010652814405078769738548913675466181551005527065309515364950610137206393257148357659666687091662749848560225453826362271704292692847596339533229088038820532086109421158575841077601268713175097874083536249006018948789413238783922845633494023608865256071962856581229890043896939025613600564283391329331452199062858930374565991634191495137939574539546
d = int(gmpy2.invert(e, phi))
c1 = M1 = pow(C1, d, n)
c2 = M2 = pow(C2, d, n)

# 一点数学运算
A = F1F2 = (pow(c1, 3) - c2) // (3*c1)

# 二元一次方程组(pip install sympy)
"""
F1 · F2 = A
F1 + F2 = c1
"""
x = Symbol('x')
y = Symbol('y')
solved_value = solve([x * y - A, x + y - c1], [x, y])

F2 = int(solved_value[0][0])
F1 = int(solved_value[0][1])
print((libnum.n2s(F1) + libnum.n2s(F2)).decode())