images
29/03/2021 08:48 am

Làm quen với Mã hoá RSA, khóa bí mật và khóa công khai cùng Python

RSA (Rivest–Shamir–Adleman) là của thuật toán về mã hóa công khai được đưa ra vào năm 1977. Đây là tên ghép của ba nhà nghiên cứu ra thuật toán này. Mục đích của RSA là để đảm bảo dữ liệu được bảo mật khi truyền thông tin.

Làm quen với Mã hoá RSA, khoá bí mật và khóa công khai cùng Python


GIỚI THIỆU RSA:


RSA (Rivest–Shamir–Adleman) là của thuật toán về mã hóa công khai được đưa ra vào năm 1977. Đây là tên ghép của ba nhà nghiên cứu ra thuật toán này. Mục đích của RSA là để đảm bảo dữ liệu được bảo mật khi truyền thông tin.


Trong RSA, việc mã hoá sẽ dùng khoá riêng để mã hoá (encryption key), trong khi việc giải mã sẽ dùng một key khác (decryption key). Khoá giải mã sẽ được lưu trữ bảo mật và không tiết lộ nên gọi là khoá bí mật - private key. Khoá mã hoá là khoá được công bố công khai - public key.

Theo cơ chế này, một nội dung tin tức trước khi được gửi đi sẽ mã hoá bởi khoá công khai, và chỉ ai có khoá bí mật mới có thể giải mã để thấy được đúng nội dung đó mà thôi. Việc có thể giải mã được khóa này sẽ vô cùng phức tạp, đặc biệt khi khoá có độ dài lớn.


Giới thiệu về thuật toán:

Thuật toán được mô tả: Chúng ta có thể tìm ra được 3 số dương (số lớn) là e, d, n sao cho với mọi số nguyên dương  < n thì ta có phép toán đồng dư sau:


Trong đó việc biết giá trị của m, e, n thì cũng rất khó tìm ra được giá trị của d. 

Thuật toán RSA chứa cặp khóa private và public key trong đó public key được tạo thành bởi ne còn private key được tạo thành bởi d.


Các bước sinh ra khoá:

  1. Chọn ra bộ số nguyên tố p, q rất lớn ngẫu nhiên và giữ bí mật

  2. Tính toán n = p.q

  3. Tính toán c = λ(n) = lcm(p-1, q-1) trong đó lcm là lowest common multiple function tức là bội số chung nhỏ nhất

  4. Chọn số e < λ(n) là số nguyên tố cùng nhau với c. e và n được chọn như là một phần của public key

  5. Tìm số d sao cho d.e ≡ 1 (λ(n)). d được giữ bí mật để tạo khóa private key


Sau quá trình này, public key sẽ chứa ne. Private key sẽ chứa d và n.


Mã hoá và giải mã:


Khi Bob muốn gửi Alice một message M, Bob sử dụng public key của Alice để mã hóa M thành c.


Alice giải mã c sử dụng private key: thông tin chứa n d:



Chúng ta hãy cùng đi vào ví dụ minh hoạ cụ thể sau:

  1. Chọn 2 số nguyên tố: (p,q) là (53,67)

  2. Tính n = p * q = 3551

  3. λ(n) = lcm(52,66) = 1716

  4. Chọn số e < 1716 là số nguyên tố cùng nhau với 1716, dễ nhất là chọn 1 số nguyên tố: 23.

  5. Tính ra số d để d * e ≡ 1(mod 1716). Ta có d = 1343 (bài toán modular multiplicative inverse) vì:

1343 * 23 = 30889  ≡ 1(mod 1716)



Vậy public key là: n = 3551, e = 23.

Và private key là n = 3551, d = 1343.


Giả sử ta cần mã hoá số m = 1000.

Mã hoá: c = me(mod n) = 100023 (mod 3551) = 2474. Dùng số 2474 để gửi đi.


Sử dụng private key để giải mã ta có:

m = 24741343(mod 3551) = 1000

Như vậy ta đã giải mã được nội dung gốc từ message mã hoá.


Bạn có thể sử dụng công cụ tính toán ở đây để thử vì các con số là rất lớn:

https://defuse.ca/big-number-calculator.htm


Chữ ký số:


Giả sử Alice muốn gửi cho Bob một message và Alice sử dụng public key của Bob để mã hoá. Tuy nhiên Bob sẽ không có cách nào biết được đây thực sự có phải là message gửi từ Alice hay không. Trong trường hợp này, chúng ta phải sử dụng một kỹ thuật gọi là ký: Signing message. Khi đó Alice sẽ phải sử dụng thuật toán RSA như trên để gửi kèm theo trong message một đoạn mã. Đoạn mã đó được tạo ra bằng cách tính toán h = Hash value của nội dung gửi. Sau đó sẽ sử dụng private key với d và n của Alice để tính toán ra phần chữ ký số gửi đi, đính kèm vào message. Bob lúc này khi nhận được message sẽ lấy ra phần chữ ký số này, sử dụng public key với n và e để tính toán ra h, rồi so sánh nó với giá trị Hash value của nội dung nhận được. Nếu bằng nhau thì sẽ xác nhận được đó chính là message gửi từ Alice. Minh hoạ như sau:

Hàm hash sẽ nhận vào chuỗi ký tự và trả ra một số. Hàm này không thể đảo ngược: không thể từ h mà tìm ra được m. Và hàm này cũng không phải là ánh xạ 1-1, tức là nhiều giá trị m khác nhau cũng có thể cho ra giá trị h giống nhau.


ÁP DỤNG RSA VỚI PYTHON

 

Giờ ta sẽ thử dùng Python để tạo key nhé. Bạn hãy thử đoạn code sau:


from Crypto.PublicKey import RSA

key = RSA.generate(2048)

publicKey = key.publickey()

print(f"Public key:  n={publicKey.n}, e={publicKey.e}")

print(f"Private key:  n={publicKey.n}, d={key.d}")


Kết quả là:


Public key:  n=19788258575027877675780020558171107887056121501488280342449228029246012492285552831015922517822961061140788495179922620401097781431970300520550595916124749703417942728958528970129536534808361088799837495627872139369338282330339881373122815286894246665173101381456120648066649816046458286611046790487749122954766673228571312506230297284804846135533256592849087311298343305980314020369147397355022588127241783240918123881586715597283425743294730990092293459282473457923534323241072620424114186825855114391035028049635985549959493661094226764701379580684646154257258579715823617027995358790136199413192054875746955983017, e=65537

Private key:  n=19788258575027877675780020558171107887056121501488280342449228029246012492285552831015922517822961061140788495179922620401097781431970300520550595916124749703417942728958528970129536534808361088799837495627872139369338282330339881373122815286894246665173101381456120648066649816046458286611046790487749122954766673228571312506230297284804846135533256592849087311298343305980314020369147397355022588127241783240918123881586715597283425743294730990092293459282473457923534323241072620424114186825855114391035028049635985549959493661094226764701379580684646154257258579715823617027995358790136199413192054875746955983017, d=4806586939528339483356609964837051840243624184539907758540202648848242563203895746173039207794432414243865481403927372234998177863123658604859009969769594130471492901754593934349941133979497080620178114544457277364244565915691602782836292423395479083004876648174313511399255358372271685682305474125676767143940693298766911821234752457583606422921991317554820803232944688450214449019815432196745656997415370457520207062224179221157065197993671007665749952674303600829647130901875454456585327812676633565315318559853074103496431525761294450319728987748438804111712836960831652572489970813507386301449299932741574268785


Nếu muốn dạng số hex bạn sử dụng

print(f"Public key: (n={hex(pubKey.n)}, e={hex(pubKey.e)})")


Để in ra dạng PEM bạn làm như sau:


publicKeyPEM = publicKey.exportKey()

privateKeyPEM = key.exportKey()

print(publicKeyPEM.decode('ascii'))

print(privateKeyPEM.decode('ascii'))


Để đảm bảo được bảo mật, các message trước khi được mã hoá sẽ sử dụng kỹ thuật Padding Schemes: Nội dung message gốc sẽ được thay đổi bằng cách add thêm nhiều dữ liệu vào các vị trí bất kỳ trong nội dung message gốc. Điều này làm cho kết quả của mã hoá trở nên khó xác định hơn. Tránh cho việc các hacker có thể dùng nhiều cách khác nhau để dò tìm ra private key.


Trong Python: để mã hoá một đoạn message dùng PKCS#1 OAEP padding:


msg = b'Hello Techzonefun'

encryptor = PKCS1_OAEP.new(publicKey)

encrypted = encryptor.encrypt(msg)

print(f"Encrypted: {binascii.hexlify(encrypted)}")


Kết quả bạn được chuỗi mã hoá sau:

Encrypted: b'63733d0ad034394649a70e8497ed9a5ef303dfa0a0c3b08cd92e33156b1e8acd6dee350ca298b054eee83a6165c7cbc235cb650e0b795781e4ec6038c1eeb59c7b7c2bc258166a3501eea08ca3dec1b4c1751659da598453136656285ce78b10e2c54b348c3e0c3e98740cd2b3798cd1b7252b1dec1bcc2d4604c7d2da7e0d5728f975df6d44b3d1b72970e9f55f3bee0b5f0a3c4e00d9d8ba1b8f68d5407a5558673977d305ace9be490d96ee48bbb1e0f01472d0a2398ee4b9a8bc7808417c4d742ed0bd5508bae95f94df60a235566663c2f35d8d28ed6cd2d328bbebe642c35d765fc351e943f9dc874bab0c64dc11655db0d0a07d29dc8add37abbedf3a'


Để giải mã, bạn dùng đoạn code sau:


decryptor = PKCS1_OAEP.new(key)

decrypted = decryptor.decrypt(encrypted)

print('Decrypted:', decrypted)


Kết quả sau khi giải mã là: Decrypted: b’Hello Techzonefun’


Chữ ký số dùng Python


Trước khi gửi msg, ta sử dụng private key để ký vào một message:


from hashlib import sha512

hash = int.from_bytes(sha512(msg).digest(), byteorder='big')

signature = pow(hash, key.d, key.n)

print("Signature:", hex(signature))


Kết quả


Signature: 0x2ec87ded4ace8757852edc2249ade3dcfaa01505d169c0bf6155f4ca3cfb9897c0de4ad84934bd2d688bc18d3ab1e6a417ef45387786486e32e0352f3029ac9ad24542e838ca6a74a4d68ce084b4e6dc00f03f33f14331aa59b18c44df08fd9f587c95c141737642dfdb805951963ee67232972c37bfb7bdada107e54d32024059e452cb625a75ef1526dd254751048167beab4b8d7b5039a30eca4a98bf13215a7b661b6b4813fd74bd8be9f4db4e9a58f85c4c7a0ae95245f98954819c39e0519bf62fb40ef2ff0801412ace80c5b7e8e7ce6e41f92c4182b1f1ab303922b6f7b12053d07c345077e567e95fc83fd07e3412451f63ec365e3a7aba7c85e2d7


Kiểm tra chữ ký số hợp lệ:


hash = int.from_bytes(sha512(msg).digest(), byteorder='big')

hashFromSignature = pow(signature, key.e, key.n)

print("Signature valid:", hash == hashFromSignature)


Kết quả: Signature valid: True


Nguồn tham khảo: Wikipedia, cryptobook.nakov.com


Source code đầy đủ:


from Crypto.PublicKey import RSA

from Crypto.Cipher import PKCS1_OAEP

import binascii

key = RSA.generate(2048)

publicKey = key.publickey()

print(f"Public key:  n={publicKey.n}, e={publicKey.e}")

print(f"Private key:  n={publicKey.n}, d={key.d}")

publicKeyPEM = publicKey.exportKey()

privateKeyPEM = key.exportKey()

print(publicKeyPEM.decode('ascii'))

print(privateKeyPEM.decode('ascii'))

msg = b'Hello Techzonefun'

encryptor = PKCS1_OAEP.new(publicKey)

encrypted = encryptor.encrypt(msg)

print(f"Encrypted: {binascii.hexlify(encrypted)}")

decryptor = PKCS1_OAEP.new(key)

decrypted = decryptor.decrypt(encrypted)

print('Decrypted:', decrypted)


# RSA sign the message

from hashlib import sha512

hash = int.from_bytes(sha512(msg).digest(), byteorder='big')

signature = pow(hash, key.d, key.n)

print("Signature:", hex(signature))


hash = int.from_bytes(sha512(msg).digest(), byteorder='big')

hashFromSignature = pow(signature, key.e, key.n)

print("Signature valid:", hash == hashFromSignature)

Mời bạn đọc thêm bài: Blockchain là gì?

- Tech Zone -

Thư giãn chút nào!!!

Bài viết liên quan