[GKCTF2020]小学生的密码学

考点:仿射密码

给自己做个记录

题目

e(x)=11x+6(mod26)

密文:welcylk

(flag为base64形式)

利用在线解密网站:https://cryptii.com/pipes/affine-cipher

flag{c29yY2VyeQ==}

[GKCTF2020]汉字的秘密

附件内容是当铺密码

dh = '田口由中人工大土士王夫井羊壮'
ds = '00123455567899'
cip = input('请输入当铺密码:')#'王壮 夫工 王中 王夫 由由井 井人 夫中 夫夫 井王 土土 夫由 土夫 井中 士夫 王工 王人 土由 由口夫'
s = ''
for i in cip:
    if i in dh:
        s += ds[dh.index(i)]
    else:
        s += ' '
print(s)#输出对应的数字
list = s.split(" ")#空格分隔,返回列表
str = ""
for i in list:
    str += chr(int(i))
print(str)#输出对应的ASCII码

输出EJ>CvSHMV7G9R9@?3k

结合FLAG的ASCII码和输出结果的ASCII码发现,差值依次为1 2 3 4

完整脚本如下:

dh = '田口由中人工大土士王夫井羊壮'
ds = '00123455567899'
cip = input('请输入当铺密码:')#'王壮 夫工 王中 王夫 由由井 井人 夫中 夫夫 井王 土土 夫由 土夫 井中 士夫 王工 王人 土由 由口夫'
s = ''
for i in cip:
    if i in dh:
        s += ds[dh.index(i)]
    else:
        s += ' '
print(s)#输出对应的数字
list = s.split(" ")#空格分隔,返回列表
str = ""
for i in list:
    str += chr(int(i))
print(str)#输出对应的ASCII码
result = ''
for i in range(0,len(list)):
    result += chr(int(list[i])+i+1)
print('result=', result, '\t\tresult.lower()=', result.lower())

考点:中国剩余定理,RSA

前提:学习中国剩余定理,python的gmpy2库

参考大佬详解https://www.cnblogs.com/MashiroSky/p/5918158.html

这里我以自己的理解不加剖析,只给算法的对中国剩余定理进行一个学习

中国剩余定理:

问:三三数余二,五五数余三,七七数余二,问数等于多少?

1.设所求数为x

x≡2(mod3)
x≡3(mod5)
x≡2(mod7)

2.列定理(这不就这么写记就行)

x≡1(mod3) x≡0(mod3) x≡0(mod3)
x≡0(mod5) x≡1(mod5) x≡0(mod5)
x≡0(mod7) x≡0(mod7) x≡1(mod7)

列出以上三组式子,分别将余数为0所对应的除数相乘

5*7=35 3*7=21 3*5=15

随后将三个结果值分别从乘1开始网上叠加作为被除数,除数分别为上式余数为1所对应的除数。随后依次计算,将余数为1随对应得1的式子记录下来

这里我将步骤写下

35*1(mod3)=3 ≠ 1 , 35*2(mod3)=1 将第二个式子保留

21*1(mod5)=1 保留

15(mod7)=1 保留

3.求值

将保留式子的被除数去除分别与第一步所列式子的余数相乘再相加 作为被除数

再将第一步所列式子的余数相乘 作为除数

计算求余的结果即为所求x数值

(70*2+21+3+15*2)(mod(3*5*7))=23

Gmpy2学习笔记

import gmpy2

gmpy2.mpz(x)# 初始化一个大整数x

gmpy2.mpfr(x)#初始化一个高精度浮点数x

C = gmpy2.powmod(M,e,n)#幂取模,结果是 C = (M^e) mod n

d = gmpy2.invert(e,n) # 求逆元,de = 1 mod n
gmpy2.is_prime(n) # 判断n是不是素数
gmpy2.gcd(a,b) # 欧几里得算法
gmpy2.gcdext(a,b) # 扩展欧几里得算法
gmpy2.iroot(x,n) # x开n次根

上题了:

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
from Crypto.Util import number
from secret import msg

assert 256 < len(msg) < 384

p, q, r = [number.getPrime(1024) for _ in range(3)]
# p = 94598296305713376652540411631949434301396235111673372738276754654188267010805522542068004453137678598891335408170277601381944584279339362056579262308427544671688614923839794522671378559276784734758727213070403838632286280473450086762286706863922968723202830398266220533885129175502142533600559292388005914561
# q = 150088216417404963893679242888992998793257903343994792697939121738029477790454833496600101388493792476973514786401036309378542808470513073408894727406158296404360452232777491992630316999043165374635001806841520490997788796152678742544032835808854339130676283497122770901196468323977265095016407164510827505883
# r = 145897736096689096151704740327665176308625097484116713780050311198775607465862066406830851710261868913835866335107146242979359964945125214420821146670919741118254402096944139483988745450480989706524191669371208210272907563936516990473246615375022630708213486725809819360033470468293100926616729742277729705727

m = number.bytes_to_long(msg)
e = 65537
for prime in [p, q, r]:
print( pow(m, e, prime) )

# 78430786011650521224561924814843614294806974988599591058915520397518526296422791089692107488534157589856611229978068659970976374971658909987299759719533519358232180721480719635602515525942678988896727128884803638257227848176298172896155463813264206982505797613067215182849559356336015634543181806296355552543
# 49576356423474222188205187306884167620746479677590121213791093908977295803476203510001060180959190917276817541142411523867555147201992480220531431019627681572335103200586388519695931348304970651875582413052411224818844160945410884130575771617919149619341762325633301313732947264125576866033934018462843559419
# 48131077962649497833189292637861442767562147447040134411078884485513840553188185954383330236190253388937785530658279768620213062244053151614962893628946343595642513870766877810534480536737200302699539396810545420021054225204683428522820350356470883574463849146422150244304147618195613796399010492125383322922

​可以看到msg相当于密文信息,相当于RSA中的c,我们先从那个for循环看,我们将m的e次方看作所求x,而对应的p,q,r则就是我们上面所学的3,5,7,而下面的结果就是上面的2,3,2,那么搞清关系后我们就知道这题先用中国剩余定理,再用RSA

接下来上脚本

import gmpy2
from Crypto.Util import number
import math
e = 65537
p = 94598296305713376652540411631949434301396235111673372738276754654188267010805522542068004453137678598891335408170277601381944584279339362056579262308427544671688614923839794522671378559276784734758727213070403838632286280473450086762286706863922968723202830398266220533885129175502142533600559292388005914561
q = 150088216417404963893679242888992998793257903343994792697939121738029477790454833496600101388493792476973514786401036309378542808470513073408894727406158296404360452232777491992630316999043165374635001806841520490997788796152678742544032835808854339130676283497122770901196468323977265095016407164510827505883
r = 145897736096689096151704740327665176308625097484116713780050311198775607465862066406830851710261868913835866335107146242979359964945125214420821146670919741118254402096944139483988745450480989706524191669371208210272907563936516990473246615375022630708213486725809819360033470468293100926616729742277729705727
m1 = q*r #公倍数#相当于35
m2 = p*r
m3 = p*q
m11 = gmpy2.invert(m1,p) #m11*m1 = 1 mod p#相当于35*2(mod3)=1的2
m22 = gmpy2.invert(m2,q)
m33 = gmpy2.invert(m3,r)
c = (m1*m11*78430786011650521224561924814843614294806974988599591058915520397518526296422791089692107488534157589856611229978068659970976374971658909987299759719533519358232180721480719635602515525942678988896727128884803638257227848176298172896155463813264206982505797613067215182849559356336015634543181806296355552543+m2* m22*49576356423474222188205187306884167620746479677590121213791093908977295803476203510001060180959190917276817541142411523867555147201992480220531431019627681572335103200586388519695931348304970651875582413052411224818844160945410884130575771617919149619341762325633301313732947264125576866033934018462843559419+m3*m33* 48131077962649497833189292637861442767562147447040134411078884485513840553188185954383330236190253388937785530658279768620213062244053151614962893628946343595642513870766877810534480536737200302699539396810545420021054225204683428522820350356470883574463849146422150244304147618195613796399010492125383322922)%(p*q*r)
N = p*q*r
N1 = (p-1)*(q-1)*(r-1)
d = gmpy2.invert(e,N1)
m = pow(c,d,N)
flag = number.long_to_bytes(m)
print (flag) #用的是先中国剩余定理,然后用了RSA

RSA部分的脚本我就不在这里解释了,网上有很多,这是最基础的,最后整理下得到flag,可以看出出题人也很用心啊