Modulo-related Attack¶
Non-coprime Modulo¶
Prasyarat¶
Ketika ada 2 public keys, N tidak saling prima
mencari GCD, lalu memperoleh p, q, dan memperoleh private key yang sesuai.
Contoh¶
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_v1_5, PKCS1_OAEP
import gmpy2
from base64 import b64decode
n1 =
n2 =
p1 = gmpy2.gcd(n1, n2)
q1 = n1 / p1
e = 65537
phin = (p1 - 1) * (q1 - 1)
d = gmpy2.invert (e, phin)
cipher = 0x68d5702b70d18238f9d4a3ac355b2a8934328250efd4efda39a4d750d80818e6fe228ba3af471b27cc529a4b0bef70a2598b80dd251b15952e6a6849d366633ed7bb716ed63c6febd4cd0621b0c4ebfe5235de03d4ee016448de1afbbe61144845b580eed8be8127a8d92b37f9ef670b3cdd5af613c76f58ca1a9f6f03f1bc11addba30b61bb191efe0015e971b8f78375faa257a60b355050f6435d94b49eab07075f40cb20bb8723d02f5998d5538e8dafc80cc58643c91f6c0868a7a7bf3bf6a9b4b6e79e0a80e89d430f0c049e1db4883c50db066a709b89d74038c34764aac286c36907b392bc299ab8288f9d7e372868954a92cdbf634678f7294096c7
plain = gmpy2.powmod(cipher, d, n1)
plain = hex(plain)[2:]
if len (plain)% 2! = 0:
plain = '0' + plain
print plain.decode('hex')
Common Modulus Attack¶
Prasyarat¶
- modulus N yang sama digunakan untuk mengenkripsi plaintext m yang sama (hanya e uang berbeda).
- e1 dan e2 koprime.
Teori¶
\[
\begin{align}
c_1 = m^{e_1}\bmod N \\
c_2 = m^{e_2}\bmod N
\end{align}
\]
Menghitung koefisien \(r\) & \(s\) dari (\(re_1+se_2=1\bmod n\)) menggunakan extended Euclidean Algorithm :
\[
\begin{align*}
c_{1}^{r}c_{2}^{s} &\equiv m^{re_1}m^{se_2}\bmod n\\
&\equiv m^{(re_1+se_2)} \bmod n\\
&\equiv m\bmod n
\end{align*}
\]
Contoh¶
#!/usr/bin/env python3
from Crypto.Util.number import long_to_bytes, bytes_to_long
from sympy import gcdex
from sys import exit
#--------data--------#
N = 0x00b0bee5e3e9e5a7e8d00b493355c618fc8c7d7d03b82e409951c182f398dee3104580e7ba70d383ae5311475656e8a964d380cb157f48c951adfa65db0b122ca40e42fa709189b719a4f0d746e2f6069baf11cebd650f14b93c977352fd13b1eea6d6e1da775502abff89d3a8b3615fd0db49b88a976bc20568489284e181f6f11e270891c8ef80017bad238e363039a458470f1749101bc29949d3a4f4038d463938851579c7525a69984f15b5667f34209b70eb261136947fa123e549dfff00601883afd936fe411e006e4e93d1a00b0fea541bbfc8c5186cb6220503a94b2413110d640c77ea54ba3220fc8f4cc6ce77151e29b3e06578c478bd1bebe04589ef9a197f6f806db8b3ecd826cad24f5324ccdec6e8fead2c2150068602c8dcdc59402ccac9424b790048ccdd9327068095efa010b7f196c74ba8c37b128f9e1411751633f78b7b9e56f71f77a1b4daad3fc54b5e7ef935d9a72fb176759765522b4bbc02e314d5c06b64d5054b7b096c601236e6ccf45b5e611c805d335dbab0c35d226cc208d8ce4736ba39a0354426fae006c7fe52d5267dcfb9c3884f51fddfdf4a9794bcfe0e1557113749e6c8ef421dba263aff68739ce00ed80fd0022ef92d3488f76deb62bdef7bea6026f22a1d25aa2a92d124414a8021fe0c174b9803e6bb5fad75e186a946a17280770f1243f4387446ccceb2222a965cc30b3929
e1 = 17
e2 = 65537
with open("flag.enc1","rb") as f1, open("flag.enc2", "rb") as f2:
c1 = bytes_to_long(f1.read())
c2 = bytes_to_long(f2.read())
#--------common modulus--------#
r, s, gcd = gcdex(e1, e2)
r = int(r)
s = int(s)
# test if e1 and e2 are coprime
if gcd != 1:
print("e1 and e2 must be coprime")
exit()
m = (pow(c1, r, N) * pow(c2, s, N)) % N
flag = long_to_bytes(m)
print(flag)
Teori: referensi lain¶
- dalam banyak kasus nilai \(s\) akan negatif, karena itu digunakan perhitungan lain
-
\(c_{2}^{s} = i^{-s}\)
\[
c_{1}^{r}i^{-s} \equiv m\bmod n
\]
Contoh¶
#!/usr/bin/python3.4
# Written by Anirudh Anand (lucif3r) : email - anirudh@anirudhanand.com
# This program will help to decrypt cipher text to plain text if you have
# more than 1 cipher text encrypted with same Modulus (N) but different
# exponents. We use extended Euclideangm Algorithm to achieve this.
__author__ = 'lucif3r'
import gmpy2
class RSAModuli:
def __init__(self):
self.a = 0
self.b = 0
self.m = 0
self.i = 0
def gcd(self, num1, num2):
"""
This function os used to find the GCD of 2 numbers.
:param num1:
:param num2:
:return:
"""
if num1 < num2:
num1, num2 = num2, num1
while num2 != 0:
num1, num2 = num2, num1 % num2
return num1
def extended_euclidean(self, e1, e2):
"""
The value a is the modular multiplicative inverse of e1 and e2.
b is calculated from the eqn: (e1*a) + (e2*b) = gcd(e1, e2)
:param e1: exponent 1
:param e2: exponent 2
"""
self.a = gmpy2.invert(e1, e2)
self.b = (float(self.gcd(e1, e2)-(self.a*e1)))/float(e2)
def modular_inverse(self, c1, c2, N):
"""
i is the modular multiplicative inverse of c2 and N.
i^-b is equal to c2^b. So if the value of b is -ve, we
have to find out i and then do i^-b.
Final plain text is given by m = (c1^a) * (i^-b) %N
:param c1: cipher text 1
:param c2: cipher text 2
:param N: Modulus
"""
i = gmpy2.invert(c2, N)
mx = pow(c1, self.a, N)
my = pow(i, int(-self.b), N)
self.m= mx * my % N
def print_value(self):
print("Plain Text: ", self.m)
def main():
c = RSAModuli()
N =
c1 =
c2 =
e1 =
e2 =
c.extended_euclidean(e1, e2)
c.modular_inverse(c1, c2, N)
c.print_value()
if __name__ == '__main__':
main()