RSA Training

• Bài viết này sẽ giới thiệu cho các bạn về những kiến thức basic nhất mà các bạn cần nắm được khi đụng vào RSA.

khả năng cao ảnh này sẽ lặp lại vào section ecc training 😅

Pre requisites

• Mình hi vọng trước khi các bạn đọc blog này thì các bạn đều đã nắm rõ / biết về các kiến thức sau:
  • Lý thuyết đồng dư (modular arithmetic)
  • Định lý Fermat nhỏ (Fermat's little theorem) hay phiên bản tổng quát hơn của nó là định lý Euler (Euler's theorem)
  • Phi hàm Euler (Euler totient function)

How it works

• RSA được chia ra làm 3 phase chính:

  • Sinh khóa (Key generation)
  • Mã hóa (Encrypt)
  • Giải mã (Decrypt)

• Trước tiên là phase sinh khóa:

  • Bước 1: Ta chọn 2 số nguyên tố p và q.
  • Bước 2: Tính n = p*q.
  • Bước 3: Tính phi hàm Euler của n
    ->
    $\varphi (n)=lcm(\varphi (p),\varphi (q))=lcm(p-1,q-1)$
  • Bước 4: Chọn 1 số e trong khoảng
    $(1,\varphi (n))$ sao cho
    $gcd(e,\varphi (n))=1$
  • Bước 5: Tính nghịch đảo modulo của e trên modulo
    $\varphi (n)$
    ->
    $d\equiv e^{-1}(mod\varphi (n))$
  • Khi này, cặp số (n, e) là public key và cặp số (n, d) là private key.

• Tiếp theo là phase mã hóa có thể được biểu diễn ngắn gọn bằng công thức sau:
  

  $$c\equiv m^e(modn)$$

• Tương tự như trên, phase giải mã cũng được biểu diễn thành công thức sau:
  

  $$m\equiv c^d(modn)$$trong đó, m chính là bản rõ (plaintext), c là bản mã (ciphertext), e là số mũ công khai (public exponent), d là số mũ bí mật (secret exponent) và n là modulo.

ex.py

import math
from Crypto.Util.number import * #pip install pycryptodome

def key_gen(bits):
    p, q = getPrime(bits), getPrime(bits)
    n = p*q
    phi = math.lcm(p-1, q-1) #phi = (p-1)*(q-1) works also
    e = 65537
    d = inverse(e, phi) #d = pow(e, -1, phi) works also
    return (n, e), (n, d)

def encrypt(m, pubkey):
    n, e = pubkey
    return pow(m, e, n)

def decrypt(c, privkey):
    n, d = privkey
    return pow(c, d, n)

Explaination

• Sau khi đã trình bày 1 loạt công thức, ta cùng đi chứng minh các công thức đó để hiểu rõ hơn bản chất của RSA.

Q.1: Tại sao lại chọn e trong khoảng

$(1,\varphi (n))$ sao cho

$gcd(e,\varphi (n))=1$?
A.1:

• Đầu tiên là tại sao e nằm trong khoảng
  $(1,\varphi (n))$, dễ dàng thấy rằng
  $e\equiv e(mod\varphi (n))vớie<\varphi (n)$. Vậy nếu
  $e>\varphi (n)$, ta có
  $e\equiv e^{\prime }(mod\varphi (n))$.
  Khi này, hủy bỏ phép modulo, ta có công thức
  $e=e^{\prime }+k\ast \varphi (n)vớik\in Z$.
  Phương trình mã hóa sẽ được viết lại thành
  $c\equiv m^e(modn)=m^{e^{\prime }+k\ast \varphi (n)}(modn)=m^{e^{\prime }}\ast m^{k\ast \varphi (n)}(modn)=m^{e^{\prime }}\ast 1^k(modn)$Như vậy có thể thấy, việc chọn 1 số e >
  $\varphi (n)$ đều sẽ được mod xuống thành 1 số trong khoảng [0,
  $\varphi (n)$)
• Tiếp theo là tại sao lại chọn
  $gcd(e,\varphi (n))=1$, đây chính là điều kiện để tồn tại số mũ bí mật d, nếu bạn đã biết về kiến thức nghịch đảo modulo hẳn bạn sẽ nhìn ra. Cụ thể;
  Để tính nghịch đảo modulo, ta sẽ cần sử dụng thuật toán Euclid mở rộng (Extended Euclid), Euclid mở rộng được phát biểu rằng ta sẽ tìm được a, b trong phương trình
  $a\ast x+b\ast y=gcd(x,y)$.
  Mình sẽ thay đổi các giá trị để giống với câu hỏi của chúng ta trong RSA
  
  $a\ast e+b\ast \varphi (n)=gcd(e,\varphi (n))$
  Nếu lấy phương trình trên xét trên mod
  $\varphi (n)$, ta có:
  
  $a\ast e\equiv 1(mod\varphi (n))$ hay
  $a\equiv e^{-1}(mod\varphi (n))$. Vậy nên, theo định nghĩa nghịch đảo modulo, ta kết luận a chính là nghịch đảo modulo của e, (trường hợp của chúng ta thì a = d).

Q.2: Tại sao để giải mã ta lại lấy

$m\equiv c^d(modn)$?
A.2: Ta biết rằng

$d\equiv e^{-1}(mod\varphi (n))$ ->

$e\ast d\equiv 1(mod\varphi (n))$. Đồng thời cũng có

$c\equiv m^e(modn)$ ->

$c^d\equiv m^{e\ast d}(modn)$
Đến đây, ta sử dụng định lý Euler ->

$m^{ed}\equiv m^{1+k\ast \varphi (n)}(modn)\equiv m\ast 1^k(modn)$

Q.3: Độ khó của bài toán RSA phụ thuộc vào thứ gì?
A.3: Độ khó của RSA phụ thuộc hoàn toàn vào việc bạn có khả năng phân tích modulo n ra thành tích các thừa số nguyên tố hay không.
decrypt(c) <- known d <- known phi(n) <- known p, q

• Về cơ bản, ta đã đi qua hết mọi phần basic trong hệ mã RSA. Nếu bạn có thắc mắc về bất cứ điều gì liên quan đến RSA, bạn có thể hỏi 1 trong các trainer hoặc liên hệ với mình qua discord tranminhprvt01

Extra information

• Khi cài đặt trong thực tế, đa số đều áp dụng định lý đồng dư Trung Hoa (Chinese Remainder Theorem) vào hệ mã RSA, mục đích là tăng tốc độ tính toán lên vì các modulo chính là p, q chứ không còn là p*q. Các bạn có thể tìm hiểu thêm với keyword là RSA CRT.
• Khi nói về chữ kí số áp dụng hệ mã RSA (RSA signature), ý tưởng cũng chỉ đơn giản là RSA, nhưng thay bản mã m thành giá trị băm của nó hash(m), cũng như sử dụng số mũ bí mật d để kí, và số mũ công khai e để xác thực.

Resources & Tools

• Đây là tài liệu RSA attacks đầu tay của mình https://www.ams.org/notices/199902/boneh.pdf. Tuy hiện tại đã có phiên bản 40 năm nên các bạn có thể tham khảo cả hai nguồn https://doi.org/10.1080/09720529.2018.1564201 (sử dụng sci-hub để truy cập)
• Nguồn tài liệu tiếp theo là bất cứ writeup về RSA nào ở trên mạng. Các bạn có thể search các writeup đó để đọc và hiểu thêm về nó.
• Các công cụ hữu ích nhất hỗ trợ bạn việc phân tích 1 số thành tích các thừa số nguyên tố là http://factordb.com và https://www.alpertron.com.ar/ECM.HTM

Practice & Homework

• Các bạn làm các bài tập sau trong Cryptohack:

set 1:
RSA Starter 1 - 5

set 2:
factoring
inferius prime
monoprime
square eyes
manyprimes
salty
modulus inutlilis

set 3:
Endless Email
infinite descent
everythings is big
cross wired

• Deadline trước buổi training sau; hình thức nộp bài: link account của các bạn trong Cryptohack kèm 1 file giải thích cách làm của các bài đã nói trên, gửi cho mình thông qua discord tranminhprvt01.
• Ngoài ra, các bạn có thể luyện thêm RSA ở các platform khác như Dreamhack, cũng như thực chiến trong CTF.
• Cuối cùng, nếu gặp bất kì khó khăn gì, trong việc hiểu bài blog này, hoặc trong việc giải bài tập, các bạn có thể hỏi 1 trong các trainer hoặc liên hệ với mình qua discord tranminhprvt01 .

The end.

• Vì 1 vài lí do kĩ thuật nên bài viết này đã được speedrun trong 2h, nên nếu có xuất hiện bất cứ vấn đề nào, mong các bạn thông cảm và feedback lại với mình.