Public Key Indexed-related Attack¶

Small Public Key Index Attack¶

Prasyarat¶

\(e\) sangat kecil, seperti 3

contoh :

\[ c\equiv m^3 \bmod N \]

maka :

\[ \begin{align*} m^3 &= c+k\times N\\ m &= \sqrt[3]{c+k\times n} \end{align*} \]

panyerang dapat enumerate \(k\) dan memperoleh akar tiga integer.

Contoh¶

XMan Summer Camp

Soal :

openssl rsa -pubin -in pubkey.pem -text -modulus

Public-Key: (4096 bit)

Modulus:

    00:b0:be:e5:e3:e9:e5:a7:e8:d0:0b:49:33:55:c6:

18: fc: 8c: 7d: 7d: 03: b8: 2e: 40: 99: 51: c1: 82: f3: 98:
from: e3: 10: 45: 80: e7: no: 70: d3: 83: yes: 53: 11: 47: 56:
    56:e8:a9:64:d3:80:cb:15:7f:48:c9:51:ad:fa:65:

db: 0b: 12: 2c: a4: 0e: 42: fa: 70: 91: 89: b7: 19:
d7: 46: E2: F6: 06: 9b: of: 11: ce: bd: 65: 0f: 14: b9: 3c:
97: 73: 52: fd: 13: b1: yes: a6: d6: e1: da: 77: 55: 02: ab:
    ff:89:d3:a8:b3:61:5f:d0:db:49:b8:8a:97:6b:c2:

05: 68: 48: 92: 84: e1: 81: f6, f1: 1E: 27: 08: 91: c8: if:
80: 01: 7b: ad: 23: 8e: 36: 30: 39: a:
    10:1b:c2:99:49:d3:a4:f4:03:8d:46:39:38:85:15:

79: c7: 52: 5a: 69: 98: 4f: 15: b5: 66: 7f: 34: 20:
eb: 26: 11: 36: 94: 7f: a1: 23: e5: 49: df: ff: 00: 60: 18:
83: of: D9: 36: fe: 41: 1e: 00: 6e: 4e: 93: D1: A0: 0b: 0f:
ea: 54: 1b: bf: c8: c5: 18: 6c: b6: 22: 05: 03:
13: 11: 0d: 64: 0c: 77: ea: 54: no: 32: 20: fc: 8f: 4c: c6:
what: 77: 15: 1e: 29: b3: e0: 65: 78: c4: 78:
    45:89:ef:9a:19:7f:6f:80:6d:b8:b3:ec:d8:26:ca:

    d2:4f:53:24:cc:de:c6:e8:fe:ad:2c:21:50:06:86:

    02:c8:dc:dc:59:40:2c:ca:c9:42:4b:79:00:48:cc:

dd: 93: 27: 06: 80: 95: ef: a0: 10: b7: f1: 96: c7: 4b:
c3: 7b: 12: 8f: 9e: 14: 11: 75: 16: 33: f7: 8b: 7b: 9e: 56:
f7: 1f: 77: a1: b4: da: ad: 3f: c5: 4b: 5e: 7e:
    a7:2f:b1:76:75:97:65:52:2b:4b:bc:02:e3:14:d5:

    c0:6b:64:d5:05:4b:7b:09:6c:60:12:36:e6:cc:f4:

    5b:5e:61:1c:80:5d:33:5d:ba:b0:c3:5d:22:6c:c2:

08: d8: the 47: 36: ba: 39: A0: 35: 44: 26: fa: e0: 06: 7:
fe: 52: d5: 26: 7d: cf: b9: c3: 88: 4f: 51: fd: df: df: 4a:
97: 94: bc: fe: 0e: 15: 57: 11: 37: 49: e6: c8: ef: 42: 1d:
You do not know how to do this.
2d: 34: 88: f7: 6d: eb: 62: bd: ef: 7b: ea: 60: 26: f2: 2a:
1d: 25: aa: 2a: 92: d1: 17: 4b:
98: 03: e6: bb: 5f: ad: 75: e1: 86: a9: 46: a1:
0f: 12: 43: f4: 38: 74: 46: cc: this: b2: 22: 2a: 96: 5c: c3:
    0b:39:29

Exponent: 3 (0x3)

Modulus=B0BEE5E3E9E5A7E8D00B493355C618FC8C7D7D03B82E409951C182F398DEE3104580E7BA70D383AE5311475656E8A964D380CB157F48C951ADFA65DB0B122CA40E42FA709189B719A4F0D746E2F6069BAF11CEBD650F14B93C977352FD13B1EEA6D6E1DA775502ABFF89D3A8B3615FD0DB49B88A976BC20568489284E181F6F11E270891C8EF80017BAD238E363039A458470F1749101BC29949D3A4F4038D463938851579C7525A69984F15B5667F34209B70EB261136947FA123E549DFFF00601883AFD936FE411E006E4E93D1A00B0FEA541BBFC8C5186CB6220503A94B2413110D640C77EA54BA3220FC8F4CC6CE77151E29B3E06578C478BD1BEBE04589EF9A197F6F806DB8B3ECD826CAD24F5324CCDEC6E8FEAD2C2150068602C8DCDC59402CCAC9424B790048CCDD9327068095EFA010B7F196C74BA8C37B128F9E1411751633F78B7B9E56F71F77A1B4DAAD3FC54B5E7EF935D9A72FB176759765522B4BBC02E314D5C06B64D5054B7B096C601236E6CCF45B5E611C805D335DBAB0C35D226CC208D8CE4736BA39A0354426FAE006C7FE52D5267DCFB9C3884F51FDDFDF4A9794BCFE0E1557113749E6C8EF421DBA263AFF68739CE00ED80FD0022EF92D3488F76DEB62BDEF7BEA6026F22A1D25AA2A92D124414A8021FE0C174B9803E6BB5FAD75E186A946A17280770F1243F4387446CCCEB2222A965CC30B3929

writing RSA key

-----BEGIN PUBLIC KEY-----

MIICIDANBgkqhkiG9w0BAQEFAAOCAg0AMIICCAKCAgEAsL7l4 + nlp + jQC0kzVcYY
/Ix9fQO4LkCZUcGC85je4xBFgOe6cNODrlMRR1ZW6Klk04DLFX9IyVGt+mXbCxIs

pA5C+nCRibcZpPDXRuL2BpuvEc69ZQ8UuTyXc1L9E7Huptbh2ndVAqv/idOos2Ff

0NtJuIqXa8IFaEiShOGB9vEeJwiRyO+AAXutI442MDmkWEcPF0kQG8KZSdOk9AON

Rjk4hRV5x1JaaZhPFbVmfzQgm3DrJhE2lH + hI + VJ3 / 8AYBiDr9k2 / kEeAG5Ok9Gg
Cw/qVBu/yMUYbLYiBQOpSyQTEQ1kDHfqVLoyIPyPTMbOdxUeKbPgZXjEeL0b6+BF

ie+aGX9vgG24s+zYJsrST1MkzN7G6P6tLCFQBoYCyNzcWUAsyslCS3kASMzdkycG

gJXvoBC38ZbHS6jDexKPnhQRdRYz94t7nlb3H3ehtNqtP8VLXn75NdmnL7F2dZdl

UitLvALjFNXAa2TVBUt7CWxgEjbmzPRbXmEcgF0zXbqww10ibMII2M5HNro5oDVE

JvrgBsf+UtUmfc+5w4hPUf3f30qXlLz+DhVXETdJ5sjvQh26Jjr/aHOc4A7YD9AC

LvktNIj3betive976mAm8iodJaoqktEkQUqAIf4MF0uYA+a7X6114YapRqFygHcP

EkP0OHRGzM6yIiqWXMMLOSkCAQM=

-----END PUBLIC KEY-----

Solusi :

source_code.py

#/usr/bin/python
# coding=utf-8
import gmpy2
from Crypto.PublicKey import RSA
from multiprocessing import Pool

pool = Pool(4)

with open('./pubkey.pem', 'r') as f:
    key = RSA.importKey(f)
    N = key.n

e = key.e
with open('flag.enc', 'r') as f:
    cipher = f.read().encode('hex')
    cipher = int(cipher, 16)

def calc(j):
    print j
    a, b = gmpy2.iroot(cipher + j * N, 3)
    if b == 1:
        m = a
        print '{:x}'.format(int(m)).decode('hex')
        pool.terminate()
        exit()

def SmallE():
    inputs = range(0, 130000000)
    pool.map(calc, inputs)
    pool.close()
    pool.join()

if __name__ == '__main__':
    print 'start'

SmallE ()

RSA Derivative Algorithm - Rabin Algorithm¶

Prasyarat¶

Algoritma Rabin memiliki ciri \(e=2\)

Teori¶

Key Generation¶

memilih \(p\) & \(q\), sehingga \(p \equiv q \equiv 3 \bmod 4\)

Enkripsi¶

\[ C = m^2 \bmod n \]

Dekripsi¶

Hitung akar \(c\) modulo \(p\) dan \(q\)

\(m_p = c^{\frac{1}{4}(p+1)} \bmod p\)

\(m_q = c^{\frac{1}{4}(q+1)} \bmod q\)
Menggunakan Extended Euclidean untuk mencari \(y_p\) dan \(y_q\), sehingga

\(y_p \cdot p + y_q \cdot q = 1\)
Menggunakan Chinese Remainder Theorem untuk mencari akar empat \(c\) modulo \(m\)

\[ \begin{align*} a &= (y_p \cdot p \cdot m_q + y_q \cdot q \cdot m_p) \bmod n\\ b &= n - a\\ c &= (y_p \cdot p \cdot m_q - y_q \cdot q \cdot m_p) \bmod n\\ d &= n - c \end{align*} \]

Salah satu dari empat nilai itu adalah plainteks asli m, meskipun yang mana dari keempat nilai tersebut yang benar tidak dapat ditentukan tanpa informasi tambahan.

Contoh¶

Enkripsi :: \(p = 7, \ q = 11\), maka \(n = 77\), misal \(m = 20\)

\[ \begin{align} c&=m^2 \bmod n\\ &=400 \bmod 77\\ &=15 \end{align} \]

Dekripsi :

\(m_p = 1\) dan \(m_q = 9\)
dengan EGCD, diperoleh \(y_p \cdot p + y_q \cdot q = 1\) dengan \(y_p = -3\) dan \(y_q = 2\)
empat kandidat pesan
\(r_1 = (-3 \cdot 7 \cdot 9 + 2 \cdot 11 \cdot 1) \bmod 77 = 64\)
\(r_2 = 77 - 64 = 13\)
\(r_3 = (-3 \cdot 7 \cdot 9 - 2 \cdot 11 \cdot 1) \bmod 77 = 20\)
\(r_4 = 77 - 20 = 57\)

diperoleh kandidat yang cocok adalah \(r_3\)

wait¶

Ciphertext:

\[ c = m^2 \ n way \]

Decryption:

Hitung \(m_p\) dan \(m_q\):

\[ \begin{align*} m_p & = \sqrt {c} \ p \\ way m_q & = \sqrt {c} \ q way \end{align*} \]

Hitung \(y_p\) dan \(y_q\) dengan extended Euclidean:

\[ y_p \cdot p + y_q \cdot q = 1 \]

Solve four plaintexts:

\[ \begin{align*} a &= (y_p \cdot p \cdot m_q + y_q \cdot q \cdot m_p) \bmod n\\ b &= n - a\\ c &= (y_p \cdot p \cdot m_q - y_q \cdot q \cdot m_p) \bmod n\\ d &= n - c \end{align*} \]

Note: Jika \(p \equiv q \equiv 3 \pmod 4\), maka

\[ \begin{align*} m_p & c = ^ {\frac {1} {4} (p + 1)} \ p \\ way m_q & c = ^ {\frac {1} {4} (q + 1)} \ q way \end{align*} \]

Secara umum, \(p \equiv q \equiv 3 \pmod 4\) memenuhi. Untuk kasus yang tidak terpenuhi, silakan merujuk ke algoritma yang sesuai.

Contoh¶

XMan Summer Camp

openssl rsa -pubin -in pubkey.pem -text -modulus

Public-Key: (256 bit)
Modulus:

    00: c2: 63: 6a: e5: c3: d8: e4: 3f: fb: 97: ab:
    1a:ac:6c:0b:f6:cd:3d:70:eb:ca:28:1b:ff:e9:7f:

    be:30:dd

Exponent: 2 (0x2)
Modulus=C2636AE5C3D8E43FFB97AB09028F1AAC6C0BF6CD3D70EBCA281BFFE97FBE30DD

writing RSA key

-----BEGIN PUBLIC KEY-----
MDowDQYJKoZIhvcNAQEBBQADKQAwJgIhAMJjauXD2OQ / + 5erCQKPGqxsC / bNPXDr
yigb / + l / vjDdAgEC
-----END PUBLIC KEY-----

\(e=2\), dengan Rabin algorithm. Pertama, hitung p & q

p=275127860351348928173285174381581152299

q=319576316814478949870590164193048041239

Write code

#!/usr/bin/python

# coding=utf-8

import gmpy2

import string

from Crypto.PublicKey import RSA



# Read public key parameters
with open('pubkey.pem', 'r') as f:

    key = RSA.importKey(f)

    N = key.n

e = key.e
with open('flag.enc', 'r') as f:

    cipher = f.read().encode('hex')

    cipher = string.atoi(cipher, base=16)

    # print cipher

print "please input p"

p = int(raw_input(), 10)

print 'please input q'

q = int(raw_input(), 10)

#算 yp和yq
inv_p = gmpy2.invert(p, q)

inv_q = gmpy2.invert(q, p)



#算mp mp and mq
mp = pow(cipher, (p + 1) / 4, p)

mq = pow(cipher, (q + 1) / 4, q)



# Calculate a, b, c, d
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)


for i in (a, b, c, d):

    s = '%x' % i
if len (s)% 2! = 0:
        s = '0' + s

    print s.decode('hex')

Get the flag, PCTF{sp3ci4l_rsa}.

Public Key Indexed-related Attack¶

Small Public Key Index Attack¶

Prasyarat¶

Contoh¶

RSA Derivative Algorithm - Rabin Algorithm¶

Prasyarat¶

Teori¶

Key Generation¶

Enkripsi¶

Dekripsi¶

Contoh¶

wait¶

Contoh¶

Sumber¶