Skip to content

RSA

RSA adalah asymmetric encryption algorithm

Properti

  • \(p\) & \(q\) prima 🔒
  • \(n = p . q\)
  • \(φ(n) = (p-1)(q-1)\) 🔒
  • \(e\) (kunci enkripsi)
    syarat: \(GCD(e, φ(n)) = 1\)
  • \(d\) (kunci dekripsi) 🔒
    \(d ≡ e^{-1} \ mod(φ(n))\)
  • \(m\) 🔒
  • \(c\)

Penurunan Rumus RSA

  • Prinsip: teorema Euler
    \(α^{φ(n)} ≡ 1 \ (mod \ n)\)

  • Syarat:

    1. \(α\) harus relatif prima terhada \(n\)
    2. \(φ(n)\) = totien euler
      fungsi yang menentukan berapa banyak dari bilangan 1,2,3,...,n yang relatif prima terhadap \(n\)
      cth. \(φ(20) = 8\)
      1,3,7,9,11,13,17,19
    3. \(φ(n) = φ(p).φ(q) = (p-1)(q-1)\)
    \[ \begin{align} α^{φ(n)} &\equiv 1 \ (\bmod n) & \text{(dipangkatkan $k$)} \\ α^{kφ(n)} &\equiv 1^k \ (\bmod n)\\ α^{kφ(n)} &\equiv 1 \ (\bmod n) & \text{(ubah $α$ jadi $m$)} \\ m^{kφ(n)} &\equiv 1 \ (\bmod n) & \text{(kali dengan $m$)} \\ m^{(kφ(n)+1)} &\equiv m \ (\bmod n) \end{align} \]

  • Misalkan e dan d dipilih sedemikian sehingga

    \[ \begin{align} e . d &\equiv 1 \ (\bmod φ(n)) \\[2ex] &\text{atau} \\[2ex] e . d &\equiv kφ(n)+1 \\[2ex] &\text{maka} \\[2ex] m^{kφ(n)+1} &\equiv m \ (\bmod \ n)\\ m^{e.d} &\equiv m \ (\bmod \ n)\\ (m^e)^d &\equiv m \ (\bmod \ n)\\ \end{align} \]

Rumus

  • Enkripsi:
    \(E_e(m) = c \equiv m^e \bmod n\)
  • Dekripsi:
    \(D_d(c) = m ≡ c^d \bmod n\)

Prosedur Pembangkitan Sepasang Kunci

  1. pilih \(p\) & \(q\)
  2. hitung \(n\)
  3. hitung \(φ(n)\)
  4. pilih \(e\)

  5. hitung kunci dekripsi dengan persamaan

    \(ed \equiv 1 (\bmod φ(n))\)

    atau

    \(d \equiv e^{-1} (\bmod φ(n))\)

    \(d\) dapat dihitung menggunakan algoritma euclidean :

    \[ d = \frac{1+kφ(n)}{e} \]

RSA Certificate

biasanya key disimpan dalam bentuk hexadesimal atau certificate (base64)

key1.pub

-----BEGIN PUBLIC KEY-----
MIIBITANBgkqhkiG9w0BAQEFAAOCAQ4AMIIBCQKCAQAuooQ4N7bQo2lnsPOZQwk6
0RRBGMbBqvbH5M3lSyw9X/crGczaLBkNcDsrhFOpECGDOnieTKc/mHH1ogKg4sH/
d708Ma/vrHu/VeT3ViCW5Uu4N21P3ON3M3mUs0+QUmMAy8egwXi+Mgfcu5KYpaw+
eIGwV6oRQ317sa+VBf4i9cebtVRQkIL8pYY3XKHfexPXXtjbCS0Q+B+GPoy1gkGV
L1zrfcaVwU7wyMz5Je9n47GXm8PsurbzsaEoCP2finuX8NmkWFP5QsCOG8Ci14RG
MajpSwaVkyFRycx8DcmzPan04P8jnKmfCVg42ufVdvMAskbh/z1qoyGdK9zJ4FdP
AgMBAAE=
-----END PUBLIC KEY-----

  1. menggunakan openssl

    openssl rsa -pubin -in key1.pub -text -noout

    output :

    RSA Public-Key: (2046 bit)
Modulus:
    2e:a2:84:38:37:b6:d0:a3:69:67:b0:f3:99:43:09:
    3a:d1:14:41:18:c6:c1:aa:f6:c7:e4:cd:e5:4b:2c:
    3d:5f:f7:2b:19:cc:da:2c:19:0d:70:3b:2b:84:53:
    a9:10:21:83:3a:78:9e:4c:a7:3f:98:71:f5:a2:02:
    a0:e2:c1:ff:77:bd:3c:31:af:ef:ac:7b:bf:55:e4:
    f7:56:20:96:e5:4b:b8:37:6d:4f:dc:e3:77:33:79:
    94:b3:4f:90:52:63:00:cb:c7:a0:c1:78:be:32:07:
    dc:bb:92:98:a5:ac:3e:78:81:b0:57:aa:11:43:7d:
    7b:b1:af:95:05:fe:22:f5:c7:9b:b5:54:50:90:82:
    fc:a5:86:37:5c:a1:df:7b:13:d7:5e:d8:db:09:2d:
    10:f8:1f:86:3e:8c:b5:82:41:95:2f:5c:eb:7d:c6:
    95:c1:4e:f0:c8:cc:f9:25:ef:67:e3:b1:97:9b:c3:
    ec:ba:b6:f3:b1:a1:28:08:fd:9f:8a:7b:97:f0:d9:
    a4:58:53:f9:42:c0:8e:1b:c0:a2:d7:84:46:31:a8:
    e9:4b:06:95:93:21:51:c9:cc:7c:0d:c9:b3:3d:a9:
    f4:e0:ff:23:9c:a9:9f:09:58:38:da:e7:d5:76:f3:
    00:b2:46:e1:ff:3d:6a:a3:21:9d:2b:dc:c9:e0:57:
    4f
Exponent: 65537 (0x10001)

  2. website https://lapo.it/asn1js/

    karena konsep certificate menggunakan ASN.1 (Abstract Syntax Notation One) wiki

    SEQUENCE (2 elem)
    SEQUENCE (2 elem)
        OBJECT IDENTIFIER 1.2.840.113549.1.1.1 rsaEncryption (PKCS #1)
        NULL
    BIT STRING (2152 bit) 001100001000001000000001000010010000001010000010000000010000000000101…
        SEQUENCE (2 elem)
        INTEGER (2046 bit) 588710189296744551230239300970957336259419103433597770268644665357352…
        INTEGER 65537

    30 82 01 21 30 0D 06 09  2A 86 48 86 F7 0D 01 01
01 05 00 03 82 01 0E 00  30 82 01 09 02 82 01 00
2E A2 84 38 37 B6 D0 A3  69 67 B0 F3 99 43 09 3A
D1 14 41 18 C6 C1 AA F6  C7 E4 CD E5 4B 2C 3D 5F
F7 2B 19 CC DA 2C 19 0D  70 3B 2B 84 53 A9 10 21
83 3A 78 9E 4C A7 3F 98  71 F5 A2 02 A0 E2 C1 FF
77 BD 3C 31 AF EF AC 7B  BF 55 E4 F7 56 20 96 E5
… skipping 160 bytes …
00 B2 46 E1 FF 3D 6A A3  21 9D 2B DC C9 E0 57 4F
02 03 01 00 01

didapat 

n = 5887101892967445512302393009709573362594191034335977702686446653573522418892872143890735426687845254111461265372034642659505979404768275167108077059156417501704452528360772945786530269462798980674453281512004838306417120731049977931108854894021202605713706620706333558929901611233909677933131192370394578396220915603163555229122761382625649400058253040521649841016574945502472294337797942436734503415011093856918753926097754850666003000379227753544168697587806628209389652238467957637121862244135658670762883123986433307510029266263945618368022864702043232089659695092442274431162305578963378970928172616133690545999
e = 65537

Tools Attacker

Sumber

  1. https://www.youtube.com/watch?v=2L-BzX1_i4o&t=309s ↩