RSA Encryption

Minh hoạt thuật toán mã hóa RSA

Nhóm 12

Nội dung trình bày

Trình bày lại định lý Euler và định lý Fermat nhỏ

1

Định lý Fermat nhỏ và Euler

Trình bày lại thuật toán  mã hóa RSA

2

RSA Encryption

Xây dựng website minh hoạ lại quá trình mã hóa của thuật toán RSA.

3

Demo minh hoạt

p

"Nếu     là số nguyên tố và     là một số nguyên không chia hết cho     thì                               sẽ chia hết cho     ".

p
a
{\displaystyle a^{p-1}-1}
p

– Pierre de Fermat

\Leftrightarrow a^{p-1} - 1 \equiv p

 Bức thư gửi ngày 18 tháng 10 năm 1640

– Leonhard Euler

" Với     là số nguyên dương bất kỳ và     là số nguyên tố cùng nhau với     thì

a^{\varphi(n)} \equiv \bar{1}\ (mod\ n), \ \forall n, a\ (a,\ n) = 1
n
a
n

"

Rivest         Shamir          Adleman

1977

Ron Rivest

Adi Shamir

Adi Shamir

Yêu cầu:

  • Khi mã hóa được kết quả thì không thể giải mã được
  • Thuật toán phải thực hiện nhanh trong điều kiện tính toán cho phép

Thuật toán RSA

x\ \xrightarrow{{encode}{}}\ m\ \xrightarrow{{decode}{}}\ x
  • Cho :

 

 

  • Mã hóa
     

Encode

Decode

  • Với :

 

 

  • Giải mã

 

x\ \xrightarrow[encode]{x^E}\ m\ \xrightarrow[decode]{(x^E)^D}\ x
\bold{p},\ \bold{q}\ là\ số\ nguyên\ tố,\\ n = p.q\\ \bold{E} \in \mathbb{U}{(Z_n)}
x\ \xrightarrow{x^E}\ m
m\ \xrightarrow{(x^E)^D}\ x
\bold{m}\ :\ số \ đã\ mã\ hóa\\ \bold{D}\ sao\ cho\\ \ D.E = \bar{1}\ (mod\ \varphi(n))
\forall x \in Z_{n},\ x^{\varphi(n)} = \bar{1 }
\Longrightarrow
E.D = \varphi(n) + 1,\xrightarrow\ (x^{E})^{D} = x

Chọn E, D

function findCoprime(p, oldPrime) {
  return new Promise((resolve, reject) => {
    if (oldPrime > p - 2n) {
      oldPrime = 1n;
    }
    for (let i = oldPrime + 1n; i < p; i++) {
      if (gcd(i, p) == 1n) {
        resolve(i);
        break;
      }
    }
    resolve(0);
  })
}
E\ \in \mathbb{U}(Z_{\varphi(n)})
D.E = \bar{1}\ (mod\ \varphi(n))\\ \Rightarrow{} D = E^{-1}\ (mod\ \varphi(n))\\ \Rightarrow{} D = E^{\varphi(n)-2}

Mã hóa C++/Javascripts

// modulo x^E in Z_n
int64_t encode(int64_t x, int64_t E, int64_t n)
{
    int64_t encode = 1;
    for (int64_t i = 0; i < E; i++)
    {
        encode = (encode * x) % n;
    }
    return encode;
}
function modulo(x, E, p) {
  return new Promise((resolve, reject) => {
    let module = 1n;
    for (let i = 0n; i < E; i++) {
      module = (module * x) % p;
    }
    resolve(module);
  });
}

https://hmthanh.github.io/rsa/

Website Demo RSA

https://hmthanh.github.io/rsa_slides/

Online Slides

https://github.com/hmthanh/rsa_encode/

RSA source code C++/Python

Thank You!

Questions?