Python套件 – RSA的計算 – pycryptodome

RSA – 公鑰加密,私鑰解密。

本篇將帶領您實際實作RSA的CTF練習題。

RSA是什麼?

RSA是一個非對稱加密演算法,利用兩個質數作為加密與解密的兩個金鑰(Key),在1978年美國麻省理工學院的 Ron Rivest, Adi Shamir, Leonard Adleman 三位發明者的名字去發展並命名,目前是最流行的公開金鑰演算法之一,可作為資料加密及數位簽署的功能。

RSA的安全取決於質因數分解的困難度,其公鑰和私鑰是一對大質數的函數。從一個公鑰和密文恢復出明文的難度,等價於分解兩個大質數之積。

質數是指在一個大於1的自然數中,除了1和此整數自身外,不能被其他自然數整除的數。

互質數是指如果兩個或兩個以上的整數的最大公因數是 1,則稱它們為互質。

其餘數學觀念與名詞可參考羊小咩撰寫的 Day 23. 非對稱式加密演算法 – RSA (觀念篇)

RSA 演算法

  1. 選兩個大質數 p 和 q (至少100位數),令 N = p • q
  2. 再計算Ø(N)=(p-1)(q-1),並選一個與Ø(N)互質數 e
  3. (e,N) 即為公開金鑰 加密法為 C = Me mod N
  4. 選一個數 d,滿足 e • d mod Ø(N) = 1
  5. d 即為解密金鑰(亦稱私有金鑰或祕密金鑰)
    解密法為 M = Cd mod N

Ø(N)為Euler’s Totient函數,其意為與N互質之個數。

加密

M 的 e 次方 除以 N 求餘數 C

解密

C 的 d 次方 除以 N 求餘數 M

例子

  1. 接收方選 p=3 , q=11 ; 此時 N = p • q = 33
  2. 找出 1 個與 ( p-1 ) x ( q-1 ) = ( 3-1 )( 11-1 ) = 2 x 10 = 20
    互質數 e=3
  3. ( e, N) = (3,33) 即為接收方的公開金鑰
  4. 接收方選一個數 d=7 當作解密金鑰,
    滿足 e • d ≡ 1 mod 20 ( 7 x 3 ≡ 1 mod 20 )
    令明文 M = 19
    加密 : C = Me mod N = 193 mod 33 = 28
    解密 : M = Cd mod N = 287 mod 33 = 19

操作演練

Mind your Ps and Qs

Category: Cryptography
AUTHOR: SARA

In RSA, a small e value can be problematic, but what about N? Can you decrypt this?
Decrypt my super sick RSA:
c: c = 62324783949134119159408816513334912534343517300880137691662780895409992760262021
n = 1280678415822214057864524798453297819181910621573945477544758171055968245116423923
e: 65537

解法

根據題目要求,我們知道
c是密文、n是p*q的結果。 e = (p-1)*(q-1)
寫成虛擬碼,我們要做的就是找到p跟q的值。

C = ciphertext
p and q = prime numbers
n = p * q
phi = (p-1) * (q-1)
e = some number that 1 < e < phi and gcd(e,phi) == 1 
d = e^(-1) mod phi

質因數分解直接算會到天荒地老,直接去查Factordb比較快。

它還有python套件呢! https://github.com/ryosan-470/factordb-python

貼上後的結果。

我們得知
p = 1899107986527483535344517113948531328331
q = 674357869540600933870145899564746495319033

接下來可以開始計算明文是什麼了,接下來才是我們的主角 – python cryptodome上場了。

PyCryptodome其實就是PyCrypto的擴充。

https://pypi.org/project/pycrypto/

但最後Released是2013年,所以還是用PyCryptodome來做吧,最後更新是2021,而且支援Python 2.7、3.5、PyPy。

https://pypi.org/project/pycryptodome/

安裝方式

pip install pycryptodome

撰寫還原明文python code

from Crypto.Util.number import inverse, long_to_bytes

c = 843044897663847841476319711639772861390329326681532977209935413827620909782846667
c = 62324783949134119159408816513334912534343517300880137691662780895409992760262021
n = 1280678415822214057864524798453297819181910621573945477544758171055968245116423923
e = 65537
p = 1899107986527483535344517113948531328331
q = 674357869540600933870145899564746495319033

phi = (p-1)*(q-1)

d = inverse(e, phi)

m = pow(c,d,n)

print(long_to_bytes(m))

實際執行

將產生的flag拿去驗證。

成功! 喜歡我的文章請給我免費拍拍手~

參考資料:

  1. RSA公開金鑰密碼機制 http://mslab.csie.asia.edu.tw/~jackjow/courses/992_InfoSecurity/ppts/IS_RSA.pdf
  2. 維基百科 – RSA加密演算法 https://zh.wikipedia.org/wiki/RSA%E5%8A%A0%E5%AF%86%E6%BC%94%E7%AE%97%E6%B3%95

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。

twenty − 9 =

Back To Top
error: Content is protected !!