Crypto-RSA-几类RSA
几类RSA1.已知m的高位题目：
123456789101112131415161718from Crypto.Util.number import getPrime,bytes_to_long,long_to_bytesfrom random import randintfrom secret import flagp = getPrime(1024)q = getPrime(1024)n = p*qprint(n)m = bytes_to_long(long_to_bytes(randint(0,30))*208+flag)assert(m.bit_length()==2044)print((m>>315)<<315)c = pow(m,3,n)print(c)#141139481892087130119093963049703776263240446335611550203664062844516140542607089345988407813973269609217188928016532051597530915599011140825564645764 ...
Crypto-RSA:选择明密文攻击
选择明密文攻击1.选择明文攻击 ：适用情况：
对输入的任意明文服务器返回 RSA 加密结果。
可以通过选择明文攻击来获取 n。
原理：
exp：
123456789101112131415161718192021222324252627282930import gmpy2def get_n(): nset = [] c2 = server_encode(2) c4 = server_encode(4) c8 = server_encode(8) nset.append(c2 * c2 - c4) nset.append(c2 * c2 * c2 - c8) c3 = server_encode(3) c9 = server_encode(9) c27 = server_encode(27) nset.append(c3 * c3 - c9) nset.append(c3 * c3 * c3 - c27) c5 = server_encode(5) c25 = server_encode(25) c12 ...
Crypto-RSA:私钥指数d攻击
私钥指数d的相关攻击1.d泄露攻击：可攻击特征:
首先当 d 泄露之后，我们自然可以解密所有加密的消息。我们甚至还可以对模数 N 进行分解。
原理:
我们知道e * d ≡ 1 (mod phi) -> e * d = k * phi + 1
所以如果得到e和d的话我们可以暴力k得到phi（一般根据phi的位数作为判断条件）
这样我们就得到了phi，如果q为p下一个素数，则可以对phi开根号，向前和向后分别取素数得到p，q。
1234567891011121314151617181920import gmpy2import sympyfrom Crypto.Util.number import *c = 227308701871338243242286750281177195505796217864184105264331005554212165092597687010635656512667133302213943018216688312232554762588815028436617087764862130174485879239972082741223788189 ...
Crypto-RSA:公钥指数e攻击
公钥指数e的相关攻击1.小公钥指数攻击可攻击特征:
e 特别小，比如 e 为 3。
加密分析：
e=3, 公钥中的加密指数e很小，但是模数n很大有RSA加密公式： C=M^e % n (C密文，M明文)则：
当M^e < n 时，C = M^e ，所以对C开方就能得到M
当M^e ＞ n 时，此时用爆破的方法假设我们 Ｍ^e / n 的商为 k 余数为C，则Ｍ^e = kn + C，对K进行爆破，只要k满足 kn + C能够开e次方就可以得明文
exp：
12345678910111213141516from gmpy2 import irootimport libnume = 0x3n = c = k = 0while 1: res = gmpy2.iroot(c+k*n,e) #c+k*n 开3次方根 能开3次方即可 #print(res) #res = (mpz(1304000448281971381981734052456302315991930504782460047879974048879 ...
Crypto-RSA:模相关攻击
模相关攻击1.暴力分解N：可攻击特征：
在 N 的比特位数小于 512 的时候，可以采用大整数分解的策略获取 p 和 q。
攻击方法：
大整数分解一般有以下两种方法：
在线数据库查询：http://factordb.com/
yafu工具 （适用于p和q相近或相差很多）
特别的，当q时p的下一个素数时，可以使用以下方法求得p。
1p = prevprime(gmpy2.iroot(n,2)[0])
p或q选取不当分解N：
当 RSA 中 p 和 q 选取不当时，我们也可以进行攻击。比如一般有以下四种情况
|p-q|很大：当|p-q| 很大时，那么其中p或q有一个值一定很小，我们可以用试除法穷举p或q。
|p-q|很小：yafu分解或开根号后在附近枚举。
q ≈ t * p ： 对n/t开根号，在附近找p。
n = p * q ≈ t * p ^ 2
n / t ≈ p ^ 2
2.多因子：可攻击特征：
N可被分解为多个素数
原理：
如果选取两个以上的素数，记为 p1,p2,p3.，它们相乘得到 n，那么：
φ(n)=(p ...
Crypto-RSA:dp或dq泄露
dp或dq泄露1.dp和dq的泄露（已知dp，dq，p，q，c）公式推导转载至https://blog.csdn.net/qq_32350719/article/details/102719279
原本dp和dq的作用是用来加快加解密速度的,但是由于dp和p,dq和q的关系密切,一旦泄漏,将造成很大的安全隐患
这里就不再次赘述了,只写出对解题相关的
dp = d mod(p-1)
dq = d mod(q-1)
InvQ * q = 1 mod p
数学推导最后得出：
m1 = c^{dq }mod q
m2 = c^{dp} mod p
m = (((m2−m1)∗p−1 mod q)p+m1) mod n
exp：
123456789101112131415import gmpy2 from Crypto.Util.number import long_to_bytes p = 8637633767257008567099653486541091171320491509433615447539162437911 ...
Crypto-RSA基础（从入门到入坟）
RSA原理+基础题目简介：RSA是非对称加密，采用公钥加密，私钥解密。
解密的难度在于大整数N的难分解性。
算法描述
1.p，q，e均已知，求解出私钥d。exp：
12345678import gmpy2p=q=e=phi = (q-1) * (p-1)d = gmpy2.invert(e,phi) print(d)
2.p，q，e，c已知，求解m。exp：
1234567891011import gmpy2p = q = e = c = n = q*pphi = (q-1) * (p-1)d = gmpy2.invert(e,phi)m = gmpy2.powmod(c,d,n)print(m)
Crypto-RSA:数论基础运算
数论基础模运算规则:模运算与基本四则运算有些相似，但是除法例外。其规则如下:
(a + b) % p = (a % p + b % p) % p
(a - b) % p = (a % p - b % p) % p
(a * b) % p = (a % p * b % p) % p
(a ^ b) % p = ((a % p)^b) % p
结合律：
((a+b) % p + c) % p = (a + (b+c) % p) % p
((a*b) % p * c)% p = (a (bc)%p) % p
交换律：
(a + b) % p = (b+a) % p
(a * b) % p = (b * a) % p
分配律：
((a +b)% p * c) % p = ((a * c) %p + (b * c) % p) % p
重要定理：
若a≡b (% p)，则对于任意的c，都有(a + c) ≡ (b + c) (%p)
若a≡b (% p)，则对于任意的正整数c，都有(a * ...
Crypto-e与φ(n)不互素时
e与φ(n)不互素时摘自大佬博客：e与φ(n)不互素时 | happi0 (gitee.io)
当gcd(e,φ(n)) != 1 的一些思路(非脚本!)
1. m ** GCD < n时原理:首先,找出gcd
1gcd(e,φ(n)) == t
那么可以找到e’满足
1e' = e // t
此时,显然gcd(e’,phi) =1,于是
123e * d = 1 + k * phi(e // t) * (d * t) = 1 + k * phie' * (d*t) = 1 + k * phi
所以可以求出dt,那么我们如何通过dt 解密呢
根据rsa基本原理,我们可以得到如下等式:
1c ** d mod n == m
1c ** d == m + k*n
等式两边同时t方
1c ** (d*t) == m**t + K*n
同时mod n得到
1c ** d*t mod n == m**t
所以,只需把d*t当作私钥解密得到的数字开t次方即可
条件:对于式子
1c ** d*t == m**t + K*n
由于结果 ...
Crypto-z3约束器
引自大佬：z3约束求解器 | happi0 (gitee.io)
z3简介:
官方: z3是由微软公司开发的一个优秀的SMT求解器（也就定理证明器），它能够检查逻辑表达式的可满足性。
人话: 解方程
通过下面一道题来展示z3的优势
题目:1234567891011121314151617#!/usr/bin/env python3import sympyimport jsonm = sympy.randprime(2**257, 2**258) M = sympy.randprime(2**257, 2**258) a, b, c = [(sympy.randprime(2**256, 2**257) % m) for _ in range(3)] x = (a + b * 3) % my = (b - c * 5) % mz = (a + c * 8) % mflag = int(open('flag', &#x ...
