CTF-CRYPTO 古典密码与RSA密码解题讲解

admin 2024年8月20日20:52:54CTF-CRYPTO 古典密码与RSA密码解题讲解已关闭评论96 views字数 14628阅读48分45秒阅读模式

CTF-CRYPTO 古典密码与RSA密码解题讲解

 

思路讲解

文章由本团队师傅[灰灰离开了]提供并授权发布

CTF-CRYPTO 古典密码与RSA密码解题讲解

古典密码:

阐述常见的古典和一些奇怪的编码

密码学的发展大概经历了三个阶段: 古典密码阶段、近代密码阶段、现代密码阶段。

ASCII编码:

ASCII 码是对英语字符与二进制位之间的关系,做了统一规定。
基本的 ASCII 字符集共有 128 个字符,其中有 96 个可打印字符,包括常用的字母、数字、标点符号等,
这128个符号,只占用了一个字节的后面7位,最前面的一位统一规定为0。
特征:只含有数字
0-9, 49-57
A-Z, 65-90
a-z, 97-122

base家族:

base家族在ctf中非常常见,常年游走在各个方向

Base16编码是将二进制文件转换成由16个字符组成的文本

base32的编码表是由(A-Z、2-7)32个可见字符构成,“=”符号用作后缀填充。

base64的编码表是由(A-Z、a-z、0-9、+、/)64个可见字符构成,“=”符号用作后缀填充。

base58的编码表相比base64少了数字0,大写字母I,O,小写字母 l (这个是L),以及符号‘+’和‘/’

base91的密文由91个字符(0-9,a-z,A-Z,!#$%&()*+,./:;<=>?@[]^_`{|}~”)组成

base100编码/解码工具(又名:Emoji表情符号编码/解码),可将文本内容编码为Emoji表情符号;同时也可以将编码后的Emoji表情符号内容解码为文本.

一些不常见的:

base92
特征:
!#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_abcdefghijklmnopqrstuvwxyz{|}
base69
ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/-*<>|
示例解密均为:flag{huihuilikaile}
base2048  示例:ڥڊתརࡐୡਛ૦۱Ԣ൲പಅఖ
base45 示例:U.C5EC2RF.$EB9DXEDWED7ECTVDZ2
base85(ACSLL85) 示例:Ao(mgHY@P9BQ\$*Bkq-kCh8"

base64还可以隐写

Base64隐写就是解码时丢掉的数据进行信息隐藏
解密代码:
# -*- coding: utf-8 -*-
import base64
b64chars = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/'
with open('stego.txt', 'rb') as f:
    bin_str = ''
    for line in f.readlines():
        stegb64 = str(line, "utf-8").strip("\n")
        tureb64 =  str(base64.b64encode(base64.b64decode(stegb64)), "utf-8").strip("\n")
        offset = abs(b64chars.index(stegb64.replace('=','')[-1])-b64chars.index(tureb64.replace('=','')[-1]))
        equalnum = stegb64.count('=') #no equalnum no offset
        if equalnum:
            bin_str += bin(offset)[2:].zfill(equalnum * 2)
        print(''.join([chr(int(bin_str[i:i + 8], 2)) for i in range(0, len(bin_str), 8)]))

在做逆向题目时还遇到过base64换表:

import base64
s1="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"
s2="替换的表"
base=b'密文'
flag=''
for i in base:
    if chr(i) != '=':
        index = s1.find(chr(i))
        flag += s2[index]
    else:
        flag +='='
print(flag)
print(base64.b64decode(flag))

以下使用工具为CaptfEncoder如有特殊会说明

Rail-fence栅栏密码

就是移位密码,可以设置栏数

下面的使用栅栏加密/解密 - Bugku CTF加密

原文:flag{huihuilikaile}
密文:fhiilullaiieghk}{ua@

还有一种w型

原文:flag{huihuilikaile}
密文:fhlliuieauia}ghlk{i

Atbash(埃特巴什码)

Atbash是一种替换密码

对应关系如下:ABCDEFGHIJKLMNOPQRSTUVWXYZ ZYXWVUTSRQPONMLKJIHGFEDCBA

flag{huihuilikaile}
uozt{sfrsfrorpzrov}

Caesar(凯撒密码)

凯撒密码是最早的替换密码,使用单表替换

flag{huihuilikaile}
iodj{kxlkxlolndloh}

Simple Substitution(简单替换)

flag{huihuilikaile}
unpm{evaevanalpani}
表:phqgiumeaylnofdxjkrcvstzwb

希尔密码

希尔密码是运用基本矩阵论原理的替换密码,由Lester S. Hill在1929年发明。

每个字母当作26进制数字:A=0, B=1, C=2… 一串字母当成n维向量,跟一个n×n的矩阵相乘,再将得出的结果模26。

flag{huihuilikaile}
edymlqdhcsjiyotpvx
key:5 17 4 15

Polybius Square Cipher(波利比奥斯方阵密码)

公元前2世纪,一个叫Polybius的希腊人设计了一种将字母编码成符号对的方法,他使用了一个称为Polybius的校验表,这个表中包含许多后来在加密系统中非常常见的成分。Polybius校验表由一个5行5列的网格组成,网格中包含26个英文字母,其中I和J在同一格中。相应字母用数对表示。在古代,这种棋盘密码被广泛使用。

flag{huihuilikaile}
CDCABDADABBAAEABBAAECAAEDBBDAECABC
key phqgiumeaylnofdxkrcvstzwb
Ciphertext characters
ABCDE

Playfair Cipher(普莱菲尔密码)

首先该密码需要秘钥,与,然后由秘钥制作相应的密码表。秘钥去重后,将秘钥依次填入5x5表格(先填纵列),剩下的格子由a-z依次填入,如果前面遇到秘钥中的字母就跳过,将i和j放在同一个格子。

flag{huihuilikaile}
EPNICVFBXESEIRESIU
key monarchybdefgiklpqstuvwxz

Vigenère Cipher(维吉尼亚密码)

维吉尼亚密码(又译维热纳尔密码)是使用一系列凯撒密码组成密码字母表的加密算法,属于多表密码的一种简单形式。

这里介绍一个密匙爆破网站:Vigenere Solver | guballa.de

Autokey Cipher(自动密钥密码)

自动密钥密码(Autokey Cipher)也是多表替换密码,与维吉尼亚密码密码类似,但使用不同的方法生成密钥。通常来说它要比维吉尼亚密码更安全。

flag{huihuilikaile}
kwammfinbctpeitto
key flag

Beaufort(博福特密码)

博福特密码,是一种类似于维吉尼亚密码的替代密码,由弗朗西斯·蒲福(Francis Beaufort)发明。它最知名的应用是M-209密码机。博福特密码属于对等加密,即加密演算法与解密演算法相同

flag{huihuilikaile}
aaaayrszldpyvlsvb
key flag

Running Key(滚动密钥密码)

滚动密钥密码具有与 Vigenere 密码相同的内部工作。区别在于如何选择密钥;Vigenere 密码使用重复

flag
mzwj
key How does the duck know that? said Victor

Affine Cipher(仿射密码)

在仿射密码中,加密函数定义为:
e(x)=(ax+b)mod26
因为这样的函数被称为仿射函数,所以这样的密码体制也称为仿射密码(可以看出,当a=1时,其对应的正是移位密码)

Baconian Cipher(培根密码)

密文特征为:AB的组合

flag
AABABABABAAAAAAAABBA

ADFGX和ADFGVX密码

ADFGX密码(ADFGX Cipher)是结合了改良过的Polybius方格替代密码与单行换位密码的矩阵加密密码,使用了5个合理的密文字母:A,D,F,G,X,这些字母之所以这样选择是因为当转译成摩尔斯电码(ADFGX密码是德国军队在一战发明使用的密码)不易混淆,目的是尽可能减少转译过程的操作错误。

ADFGVX密码实际上就是ADFGX密码的扩充升级版,一样具有ADFGX密码相同的特点,加密过程也类似,不同的是密文字母增加了V,使得可以再使用10数字来替换明文。

棋盘密码

棋盘密码(Checkerboard Cipher)是使用一个波利比奥斯方阵和两个密钥作为密阵的替换密码,通常在波利比奥斯方阵中J字母往往被包含在I字母中。

古典还有很多,是记不全的,这里推荐随波逐流这个工具,它包含很多密码,并且可以一键解密,网址:随波逐流信息安全网 (1o1o.xyz)

一些特殊编码:

以下加密使用toolsfx工具箱

与佛论禅:

密文特征:

佛曰:遠呐切多梵醯罰藐梵謹梵殿梵羯諳怖罰以怯諦皤即俱呼度訶諳迦罰喝皤是罰室朋諳夜者隸諳特耨呐上罰所伽羯度梵藐侄朋怯所呐闍哆彌一梵喝呐亦罰依侄吉他皤不俱耶諳參俱尼密呐耨怯波

六十四卦:

密文特征:

蛊随损颐蛊履离明夷鼎困噬嗑明夷鼎困噬嗑丰井困离颐井困损噬嗑姤师

兽音:

~呜嗷嗷嗷嗷呜啊嗷啊呜呜嗷呜呜~嗷嗷~啊嗷啊呜嗷嗷~嗷~嗷~呜呜嗷呜啊嗷嗷嗷呜啊呜~啊呜嗷呜呜~嗷~~啊嗷啊呜嗷呜嗷嗷~嗷~呜呜嗷啊嗷嗷嗷嗷呜啊嗷啊~呜嗷呜呜~呜~嗷啊嗷啊呜嗷嗷呜嗷~嗷~呜呜嗷啊~嗷嗷嗷呜啊嗷~嗷呜嗷呜呜~嗷嗷啊啊嗷啊呜嗷嗷~嗷~嗷~呜呜嗷啊嗷嗷嗷嗷呜啊嗷~~呜嗷呜呜~嗷~嗷啊嗷啊呜嗷呜啊嗷啊

天干地支:

壬申丙寅丙寅己酉丁丑丁未辛亥癸酉乙卯庚申戊午庚午乙亥己未戊午己巳甲辰乙酉壬辰丙寅癸巳乙酉己亥乙巳辛丑乙丑

新佛曰:

新佛曰:諸閦隸閦僧降吽諸陀摩隸僧缽薩閦願耨咤陀願閦羅咤喃閦莊閦隸念閦諦耨閦夷阿闍閦劫閦所願閦隸閦蜜閦囉閦修閦祗閦如念囑囑閦

熊曰:

熊曰:呋食食取現住盜嗷告告人囑破噗寶嗡和嚁噤咯人和嘶啽更

百家姓:

杨吕褚朱{秦陶尤秦陶尤吕尤何褚尤吕韩}

阴阳怪气:

就 这 ¿ 就 这 ¿ 不 会 吧 ?不 会 吧 ?就 这 ¿ 就 这 ¿ 不 会 吧 ?不 会 吧 ?就 这 ¿ 就 这 ¿ 就 这 ¿ 不 会 吧 ?不 会 吧 ?就 这 ¿ 不 会 吧 ?不 会 吧 ?就 这 ¿ 就 这 ¿ 就 这 ¿ 就 这 ¿ 不 会 吧 ?不 会 吧 ?就 这 ¿ 就 这 ¿ 就 这 ¿ 就 这 ¿ 不 会 吧 ?就 这 ¿ 就 这 ¿ 不 会 吧 ?不 会 吧 ?就 这 ¿ 就 这 ¿ 不 会 吧 ?不 会 吧 ?不 会 吧 ?就 这 ¿ 就 这 ¿ 不 会 吧 ?不 会 吧 ?不 会 吧 ?不 会 吧 ?就 这 ¿ 不 会 吧 ?不 会 吧 ?就 这 ¿ 就 这 ¿ 不 会 吧 ?不 会 吧 ?就 这 ¿ 不 会 吧 ?就 这 ¿ 就 这 ¿ 就 这 ¿ 就 这 ¿ 就 这 ¿ 不 会 吧 ?不 会 吧 ?不 会 吧 ?就 这 ¿ 不 会 吧 ?就 这 ¿ 不 会 吧 ?就 这 ¿ 就 这 ¿ 不 会 吧 ?不 会 吧 ?就 这 ¿ 不 会 吧 ?就 这 ¿ 就 这 ¿ 不 会 吧 ?就 这 ¿ 就 这 ¿ 不 会 吧 ?不 会 吧 ?就 这 ¿ 不 会 吧 ?就 这 ¿ 就 这 ¿ 就 这 ¿ 就 这 ¿ 就 这 ¿ 不 会 吧 ?不 会 吧 ?不 会 吧 ?就 这 ¿ 不 会 吧 ?就 这 ¿ 不 会 吧 ?就 这 ¿ 就 这 ¿ 不 会 吧 ?不 会 吧 ?就 这 ¿ 不 会 吧 ?就 这 ¿ 就 这 ¿ 不 会 吧 ?就 这 ¿ 就 这 ¿ 不 会 吧 ?不 会 吧 ?就 这 ¿ 不 会 吧 ?不 会 吧 ?就 这 ¿ 就 这 ¿ 就 这 ¿ 就 这 ¿ 不 会 吧 ?不 会 吧 ?就 这 ¿ 不 会 吧 ?就 这 ¿ 就 这 ¿ 不 会 吧 ?就 这 ¿ 就 这 ¿ 不 会 吧 ?不 会 吧 ?就 这 ¿ 不 会 吧 ?就 这 ¿ 不 会 吧 ?不 会 吧 ?就 这 ¿ 就 这 ¿ 不 会 吧 ?不 会 吧 ?就 这 ¿ 就 这 ¿ 就 这 ¿ 就 这 ¿ 不 会 吧 ?就 这 ¿ 就 这 ¿ 不 会 吧 ?不 会 吧 ?就 这 ¿ 不 会 吧 ?就 这 ¿ 就 这 ¿ 不 会 吧 ?就 这 ¿ 就 这 ¿ 不 会 吧 ?不 会 吧 ?就 这 ¿ 不 会 吧 ?不 会 吧 ?就 这 ¿ 就 这 ¿ 就 这 ¿ 就 这 ¿ 不 会 吧 ?不 会 吧 ?就 这 ¿ 就 这 ¿ 不 会 吧 ?就 这 ¿ 不 会 吧 ?就 这 ¿ 就 这 ¿ 不 会 吧 ?不 会 吧 ?不 会 吧 ?不 会 吧 ?不 会 吧 ?就 这 ¿ 不 会 吧 ?

brain fuck

Brainfuck,简称BF,是一种极小化的程序语言,由Urban Müller在1993年创造。Fuck在英语中是脏话,所以这种语言有时称为Brainf*ckBrainf\***,或者只用简称。

+++++++++[>+++++++++++<-]>+++.++++++.>++++++++[>++++++++++++<-]>+.++++++.>++++++++++[>++++++++++++<-]>+++.>+++++++++[>++++++++++++<-]>----.>+++++++++[>+++++++++++++<-]>.>+++++++++[>++++++++++++<-]>---.-.>+++++++++[>+++++++++++++<-]>.>+++++++++[>++++++++++++<-]>---.+++.---.++.>++++++++[>++++++++++++<-]>+.++++++++.+++.-------.>+++++++++++[>+++++++++++<-]>++++.

JSfuck

CTF在线工具-在线JSfuck加密|在线JSfuck解密|JSfuck|JSfuck原理|JSfuck算法 (hiencode.com)

(![]+[])[+[]]+(![]+[])[!+[]+!+[]]+(![]+[])[+!+[]]+(![]+[+[]]+([]+[])[([][(![]+[])[+[]]+([![]]+[][[]])[+!+[]+[+[]]]+(![]+[])[!+[]+!+[]]+(![]+[])[!+[]+!+[]]]+[])[!+[]+!+[]+!+[]]+(!![]+[][(![]+[])[+[]]+([![]]+[][[]])[+!+[]+[+[]]]+(![]+[])[!+[]+!+[]]+(![]+[])[!+[]+!+[]]])[+!+[]+[+[]]]+([][[]]+[])[+!+[]]+(![]+[])[!+[]+!+[]+!+[]]+(!![]+[])[+[]]+(!![]+[])[+!+[]]+([][[]]+[])[+[]]+([][(![]+[])[+[]]+([![]]+[][[]])[+!+[]+[+[]]]+(![]+[])[!+[]+!+[]]+(![]+[])[!+[]+!+[]]]+[])[!+[]+!+[]+!+[]]+(!![]+[])[+[]]+(!![]+[][(![]+[])[+[]]+([![]]+[][[]])[+!+[]+[+[]]]+(![]+[])[!+[]+!+[]]+(![]+[])[!+[]+!+[]]])[+!+[]+[+[]]]+(!![]+[])[+!+[]]])[!+[]+!+[]+[+[]]]

一些密码学相关:

md5:

摘自维基百科

MD5消息摘要算法(英语:MD5 Message-Digest Algorithm),一种被广泛使用的密码散列函数,可以产生出一个128位(16个字符(BYTES))的散列值(hash value),用于确保信息传输完整一致。MD5由美国密码学家罗纳德·李维斯特(Ronald Linn Rivest)设计,于1992年公开,用以取代MD4算法。这套算法的程序在 RFC 1321 中被加以规范。

将数据(如一段文字)运算变为另一固定长度值,是散列算法的基础原理。

327a6c4304ad5938eaf0efb6cc3e53dc

32位密文

Rabbit

Rabbit加密算法是一种流密码算法,其工作原理基于非线性的置换和混淆操作。Rabbit算法使用一个128位的密钥和一个64位的初始化向量(IV)来生成密钥流,然后将密钥流与明文数据进行异或运算来实现加密和解密。

通常开头为 U2FsdGVkX1 有时aes,des也以此为开头

CTF-CRYPTO 古典密码与RSA密码解题讲解

RSA

摘自维基百科

RSA加密算法是一种非对称加密算法,在公开密钥加密和电子商业中被广泛使用。RSA是由罗纳德·李维斯特(Ron Rivest)、阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman)在1977年一起提出的。当时他们三人都在麻省理工学院工作。RSA 就是他们三人姓氏开头字母拼在一起组成的。[1]

1973年,在英国政府通讯总部工作的数学家克利福德·柯克斯(Clifford Cocks)在一个内部文件中提出了一个与之等效的算法,但该算法被列入机密,直到1997年才得到公开。[2]

对极大整数做因数分解的难度决定了 RSA 算法的可靠性。换言之,对一极大整数做因数分解愈困难,RSA 算法愈可靠。

原理可以看这个:RSA算法原理(一) - 阮一峰的网络日志 (ruanyifeng.com)

使用python代码简单实现

from Crypto.Util.number import *   #导入密码库
p = getPrime(512)  #生成512位素数
q = getPrime(512)
print(p,q)
n = p*q
e = 65537
m = b'flag'
m = bytes_to_long(m)
c = pow(m,e,n)  #加密m
print(c)

解密:

p = 7538900443375154852431280671234268444600583430283881202775531362193800955458762896783209821388619129865492702493804082951643210169938978243990418982425319
q = 12915822712631386581647657442248047453688459372149761887857556513515978145790527853243213085146445652144574756002977066484215528225335732525878299484676431
n = p*q
phi = (p-1)*(q-1)
d = inverse(e,phi)
c = 67535155202761484017935513256953617516906600066741623311948938806303062792879503980935481882345869739023439793360271949435137738997669399879241714666881396912452886271853142019923582781708389636605122342075512907759974063650620484330007925050461699751495382236891740825775048298749174210879928543384932861515
print(long_to_bytes(pow(c,d,n)))

解密rsa的主要目标就是得到p,q,因为解密所需私匙需要使用p,q。而因数分解是一大难题,这也就保证了rsa的安全性

下面提供常见的攻击方式代码:

共享素数:

题目给出两个n

from Crypto.Util.number import *
from gmpy2 import powmod as gmpy2
c = 
n1 = 
n2 = 
e = 65537
q = gmpy2.gcd(n1, n2)  # 求n1和n2的最大公因数
p1 = n1 // q
p2 = n2 // q
fn1 = (q - 1) * (p2 - 1)  # 求下面的&n
fn2 = (q - 1) * (p1 - 1)  # 求上面的&n
d1 = inverse(e, fn1)  # (de)mod((p-1)*(q-1))=1  求到第一次解密密钥d1
d2 = inverse(e, fn2)  # 求出第二次解密密钥d2
m = pow(c, d2, n2)  # 先对第二次加密进行解密
m = pow(m, d1, n1)  # 用第二次解密结果继续解密
print(long_to_bytes(m))

共模攻击:

题目给出两个e,c

from gmpy2 import *
from Crypto.Util.number import *

n = 

e1 = 2767
e2 = 3659

c1 = 
c2 = 

_, s1, s2 = gcdext(e1, e2)

m = powmod(c1, s1, n) * powmod(c2, s2, n) % n
print(long_to_bytes(m))

e过小:

e为3,2很小的数,可以通过爆破得到m

from gmpy2 import *
from Crypto.Util.number import *
c = 
n = 
e = 65537
for k in range(100000000):
    cc = c + k*n
    res = iroot(cc, e)
    if res[1]:
        m = res
        break
print(m)
print('k:',k) # 11

pq接近:

pq很接近的时候可以爆破得到p,q

题目出现gmpy2.next_prime()

import gmpy2
from Crypto.Util.number import *
n = 
c = 
i = gmpy2.iroot(n, 2)[0]
while not gmpy2.is_prime(i):
    i += 1
p = i
q = n // p
e = 65537
if n == p*q:
    print("p: ",p,"q: ",q)
d =inverse(e, (p - 1) * (q - 1))
m = pow(c, d, n)
print(long_to_bytes(m))

wiener(维纳)攻击:

当e特别大的时候可以使用连分数

import gmpy2
import libnum

def continuedFra(x, y):
    """计算连分数
    :param x: 分子
    :param y: 分母
    :return: 连分数列表
    """
    cf = []
    while y:
        cf.append(x // y)
        x, y = y, x % y
    return cf
def gradualFra(cf):
    """计算传入列表最后的渐进分数
    :param cf: 连分数列表
    :return: 该列表最后的渐近分数
    """
    numerator = 0
    denominator = 1
    for x in cf[::-1]:
        # 这里的渐进分数分子分母要分开
        numerator, denominator = denominator, x * denominator + numerator
    return numerator, denominator
def solve_pq(a, b, c):
    """使用韦达定理解出pq,x^2−(p+q)∗x+pq=0
    :param a:x^2的系数
    :param b:x的系数
    :param c:pq
    :return:p,q
    """
    par = gmpy2.isqrt(b * b - 4 * a * c)
    return (-b + par) // (2 * a), (-b - par) // (2 * a)
def getGradualFra(cf):
    """计算列表所有的渐近分数
    :param cf: 连分数列表
    :return: 该列表所有的渐近分数
    """
    gf = []
    for i in range(1, len(cf) + 1):
        gf.append(gradualFra(cf[:i]))
    return gf


def wienerAttack(e, n):
    """
    :param e:
    :param n:
    :return: 私钥d
    """
    cf = continuedFra(e, n)
    gf = getGradualFra(cf)
    for d, k in gf:
        if k == 0: continue
        if (e * d - 1) % k != 0:
            continue
        phi = (e * d - 1) // k
        p, q = solve_pq(1, n - phi + 1, n)
        if p * q == n:
            return d


n= 
e= 
c= 

d=wienerAttack(e, n)
m=pow(c, d, n)
print(libnum.n2s(m).decode())

低加密指数广播攻击:

当有多组n,c的时候,且e小

import libnum
from gmpy2 import invert, gcd, iroot

def op(x):
    res = 1
    for i in x:
        res *= i
    return res

def CRT(m, a):
    assert (len(m) == len(a))
    M = op(m)
    sum = 0
    for m, a in zip(m, a):
        Mi = M // m
        ti = invert(Mi, m)
        sum += a * ti * Mi
    return sum % M
def GCRT(m, a):
    assert (len(m) == len(a))
    curm, cura = m[0], a[0]
    for m, a in zip(m[1:], a[1:]):
        d = gcd(curm, m)
        c = a - cura
        assert (c % d == 0)
        K = c // d * invert(curm // d, m // d)
        cura += curm * K
        curm = curm * m // d
    return cura % curm

e= 23
n= [, , , , , , ]
c= [, , , , , , ]

m = CRT(n, c)
m1 = iroot(m, e)  # 开e次方
print(m1)
print(libnum.n2s(int(m1[0])))

dp泄露:

import libnum
import gmpy2
n= 
e= 65537
dp= 
c= 
for i in range(1,65535):
    p=(dp*e-1)//i+1
    if n%p==0:
        q=n//p
        break
phi_n= (p-1)*(q-1)
d=gmpy2.invert(e,phi_n)
m=pow(c,d,n)
print(m)
flag=libnum.n2s(int(m)).decode()
print(flag)

dp,dq泄露:

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= 
q= 
dq= 
dp= 
c= 
decrypt(dp,dq,p,q,c)

n是p的r次方:

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

NC不互素:

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

p高位攻击:

题目对p进行位移操作需要使用sage

n = 
p4=
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)
    print (p)
    print (n/p)

m高位攻击:

需要sage

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= 
e= 3
c= 
high_m= 

phase2(high_m, n, c)

p-1光滑:

光滑数:指可以分解为小素数乘积的正整数

from Crypto.Util.number import *
from gmpy2 import *
n =
e = 65537
c = 
a = 2
m = 2
while True:
    a = powmod(a, m, n)
    p = gcd(a-1, n)
    if p != 1 and p != n:
        break
    m += 1
print(p)
q = n // p

phi = (p-1)*(q-1)
d = invert(e, phi)
m = powmod(c, d, n)
print(long_to_bytes(m))

p+1光滑:

from Crypto.Util.number import *
from gmpy2 import *
from itertools import count

n = 
e = 65537
c = 

def mlucas(v, a, n):
    v1, v2 = v, (v ** 2 - 2) % n
    for bit in bin(a)[3:]: v1, v2 = ((v1 ** 2 - 2) % n, (v1 * v2 - v) % n) if bit == "0" else (
        (v1 * v2 - v) % n, (v2 ** 2 - 2) % n)
    return v1

def primegen():
    yield 2
    yield 3
    yield 5
    yield 7
    yield 11
    yield 13
    ps = primegen()  # yay recursion
    p = ps.__next__() and ps.__next__()
    q, sieve, n = p ** 2, {}, 13
    while True:
        if n not in sieve:
            if n < q:
                yield n
            else:
                next, step = q + 2 * p, 2 * p
                while next in sieve:
                    next += step
                sieve[next] = step
                p = ps.__next__()
                q = p ** 2
        else:
            step = sieve.pop(n)
            next = n + step
            while next in sieve:
                next += step
            sieve[next] = step
        n += 2

def ilog(x, b):  # greatest integer l such that b**l <= x.
    l = 0
    while x >= b:
        x /= b
        l += 1
    return l

def attack(n):
    for v in count(1):
        for p in primegen():
            e = ilog(isqrt(n), p)
            if e == 0:
                break
            for _ in range(e):
                v = mlucas(v, p, n)
            g = gcd(v - 2, n)
            if 1 < g < n:
                return int(g), int(n // g)  # g|n
            if g == n:
                break

p, q = attack(n)


phi = (p-1)*(q-1)
d = invert(e, phi)
m = powmod(c, d, n)
print(long_to_bytes(m))

rabin算法:

e为2,严格来说不算rsa

from Crypto.Util.number import *
from gmpy2 import *
p = 
q = 
e = 2
c = 
def rabin_attack(c, n, p, q):
    c1 = powmod(c, (p+1)//4, p)
    c2 = powmod(c, (q+1)//4, q)
    cp1 = p - c1
    cp2 = q - c2

    t1 = invert(p, q)
    t2 = invert(q, p)

    m1 = (q*c1*c2 + p*c2*t1) % n
    m2 = (q*c1*t2 + p*cp2*t1) % n
    m3 = (q*cp1*t2 + p*c2*t1) % n
    m4 = (q*cp1*t2 + p*cp2*t1) % n

    return m1, m2, m3, m4
ms = rabin_attack(c, p*q, p, q)
for m in ms:
    print(long_to_bytes(m))

剪枝:

a1^b1:
from Crypto.Util.number import *
import sys

sys.setrecursionlimit(1500)

# part1,剪枝
a1 = 
b1 = 
c1 = 
e = 65537
a1 = "0" + str(bin(a1)[2:])


def find(p, q):
    l = len(p)
    tmp0 = p + (1024 - l) * "0"
    tmp1 = p + (1024 - l) * "1"
    tmq0 = q + (1024 - l) * "0"
    tmq1 = q + (1024 - l) * "1"
    if (int(tmp0, 2) < int(tmq0, 2)):
        return
    if (int(tmp0, 2) * int(tmq0, 2) > b1):
        return
    elif (int(tmp1, 2) * int(tmq1, 2) < b1):
        return

    if (l == 1024):
        pp = int(tmp0, 2)
        qq = int(tmq0, 2)
        d = inverse(e, (pp - 1) * (qq - 1))
        m = long_to_bytes(pow(c1, d, pp * qq))
        print(str(m)[2:-1], end="")

    else:
        if (a1[l] == "1"):
            find(p + "1", q + "0")
            find(p + "0", q + "1")
        else:
            find(p + "0", q + "0")
            find(p + "1", q + "1")


tempp = ""
tempq = ""
find(tempp, tempq)
p ^ _q:

p与q的反方向二进制的异或值

from Crypto.Util.number import *
import sys
sys.setrecursionlimit(1500)

pxorq = 
n =
c = 
e = 65537
pxorq = str(bin(pxorq)[2:]).zfill(256)

def find(ph,qh,pl,ql):
    l = len(ph)
    tmp0 = ph + (256-2*l)*"0" + pl
    tmp1 = ph + (256-2*l)*"1" + pl
    tmq0 = qh + (256-2*l)*"0" + ql
    tmq1 = qh + (256-2*l)*"1" + ql
    if(int(tmp0,2)*int(tmq0,2) > n):
        return 
    if(int(tmp1,2)*int(tmq1,2) < n):
        return
    if(int(pl,2)*int(ql,2) % (2**(l-1)) != n % (2**(l-1))):
        return

    if(l == 128):
        pp0 = int(tmp0,2)
        if(n % pp0 == 0):
            pf = pp0
            qf = n//pp0
            phi = (pf-1)*(qf-1)
            d = inverse(e,phi)
            m1 = pow(c,d,n)
            print(long_to_bytes(m1))
            exit()

    else:
        if(pxorq[l] == "1" and pxorq[255-l] == "1"):
            find(ph+"1",qh+"0","1"+pl,"0"+ql)
            find(ph+"0",qh+"0","1"+pl,"1"+ql)
            find(ph+"1",qh+"1","0"+pl,"0"+ql)
            find(ph+"0",qh+"1","0"+pl,"1"+ql)
        elif(pxorq[l] == "1" and pxorq[255-l] == "0"):
            find(ph+"1",qh+"0","0"+pl,"0"+ql)
            find(ph+"0",qh+"0","0"+pl,"1"+ql)
            find(ph+"1",qh+"1","1"+pl,"0"+ql)
            find(ph+"0",qh+"1","1"+pl,"1"+ql)
        elif(pxorq[l] == "0" and pxorq[255-l] == "1"):
            find(ph+"0",qh+"0","1"+pl,"0"+ql)
            find(ph+"0",qh+"1","0"+pl,"0"+ql)
            find(ph+"1",qh+"0","1"+pl,"1"+ql)
            find(ph+"1",qh+"1","0"+pl,"1"+ql)
        elif(pxorq[l] == "0" and pxorq[255-l] == "0"):
            find(ph+"0",qh+"0","0"+pl,"0"+ql)
            find(ph+"1",qh+"0","0"+pl,"1"+ql)
            find(ph+"0",qh+"1","1"+pl,"0"+ql)
            find(ph+"1",qh+"1","1"+pl,"1"+ql)

find("1","1","1","1")

以上就是一些rsa常见的攻击脚本,(写了一个十分low的工具,方便模板题使用:huihuilikaile (huihuilikaile) (github.com))

免责声明:文章中涉及的程序(方法)可能带有攻击性,仅供安全研究与教学之用,读者将其信息做其他用途,由读者承担全部法律及连带责任,本站不承担任何法律及连带责任;如有问题可邮件联系(建议使用企业邮箱或有效邮箱,避免邮件被拦截,联系方式见首页),望知悉。
  • 左青龙
  • 微信扫一扫
  • weinxin
  • 右白虎
  • 微信扫一扫
  • weinxin
admin
  • 本文由 发表于 2024年8月20日20:52:54
  • 转载请保留本文链接(CN-SEC中文网:感谢原作者辛苦付出):
                   CTF-CRYPTO 古典密码与RSA密码解题讲解https://cn-sec.com/archives/3082473.html
                  免责声明:文章中涉及的程序(方法)可能带有攻击性,仅供安全研究与教学之用,读者将其信息做其他用途,由读者承担全部法律及连带责任,本站不承担任何法律及连带责任;如有问题可邮件联系(建议使用企业邮箱或有效邮箱,避免邮件被拦截,联系方式见首页),望知悉.