Asymmetric key cryptography

Sa araling ito, titingnan natin ang asymmetric key cryptography na siyang pundasyon ng maraming ligtas na pakikipag-ugnayan sa network ngayon.

Sa pagtatapos ng aralin, matatalakay natin ang:

Ano ang asymmetric key cryptography
Paggamit ng asymmetric key cryptography, kabilang ang key exchange at digital signatures
Seguridad ng asymmetric key cryptography sa pangkalahatan
Karagdagang detalye tungkol sa RSA, DSA, at Elliptic Curves na mga algorithm at seguridad
Ilang halimbawa ng Python code na nagpapakita kung paano gumagana ang mga algorithm sa praktiko
Mga banta sa mga algorithm na ito mula sa parehong klasikal at quantum na mga computer

Panimula sa asymmetric key cryptography

Tulad ng natutunan natin sa huling aralin, ang symmetric key cryptography ay napakabilis at mahusay para sa pagprotekta ng impormasyon, ngunit mayroon itong ilang limitasyon:

Habang dumarami ang mga partido na gustong mag-palitan ng ligtas na impormasyon, ang bilang ng mga kinakailangang key ay lumalaki nang combinatorially. Walang mekanismong ligtas na maipamahagi ang mga key na ito sa pagitan ng mga nagpadala at tatanggap.
Walang probisyon para sa non-repudiation. Ang sinumang partido ay maaaring mag-decrypt o mag-encrypt ng mga mensahe nang walang paraan upang matiyak na natanggap ang isang mensahe o kung saan ito nanggaling.

Ang solusyon sa parehong mga problemang ito ay ibinibigay ng asymmetric key cryptography (AKC), na kilala rin bilang public key cryptography (PKC), na siyang isa sa mga pundasyon ng modernong digital na seguridad.

Ang asymmetric key cryptography (AKC) ay gumagamit ng pares ng mga key — isa ay pampubliko, isa ay pribado. Ang mga pampubliko at pribadong key ay cryptographically na magkaugnay at karaniwang nalilikha nang sabay bilang isang key pair gamit ang isang espesyalisadong mathematical na algorithm. Ang pampublikong key, tulad ng iminumungkahi ng pangalan nito, ay dapat na malayang ipamahagi, habang ang pribadong key ay pinananatiling lihim ng partido na bumubuo ng key pair. Ang seguridad ng mga komunikasyon gamit ang asymmetric key pairs ay natitiyak hangga't nananatiling kumpidensyal ang pribadong key.

Larawan 1. Asymmetric Key Encryption

Larawan 1. Asymmetric Key Encryption

Nag-aalok ang AKC ng ilang kapaki-pakinabang na mga function, tulad ng:

Encryption at decryption upang paganahin ang pagiging kumpidensyal ng mga komunikasyon.
Digital signatures upang matiyak ang pagiging tunay, integridad, at non-repudiation.
Ligtas na key exchange upang mapadali ang kasunod na paggamit ng mga symmetric cryptosystem.

Sa mga modernong aplikasyon, ang AKC ay pangunahing ginagamit para sa mga digital signature at ligtas na key exchange. Sa araling ito, ipinapakilala natin ang dalawang pangunahing function na ito, at pagkatapos ay tatalakayin natin ang ilang mga variation ng cryptographic protocol para sa mga function na ito.

Key exchange gamit ang asymmetric key cryptography

Isa sa mga pundamental na problema sa cryptography ay ang ligtas na pagpapalitan ng mga key. Halimbawa, kung dalawang partido ang gustong gumamit ng symmetric encryption, kailangan ng parehong partido ang parehong key para mag-encrypt at mag-decrypt ng mga mensahe. Ngunit paano sila ligtas na makakapagpalitan ng key? Tinutugunan ito ng asymmetric key cryptography sa pamamagitan ng interactive at non-interactive na mga mekanismo ng key exchange.

Interactive key exchange

Ang isang interactive key exchange protocol ay tumutukoy sa isang paraan kung saan ang dalawang partido ay nakikipagtulungan upang lumikha ng isang shared secret key sa pamamagitan ng isang hindi ligtas na channel ng komunikasyon. Ang shared secret key na ito ay maaaring gamitin para sa mga gawain ng symmetric encryption at decryption.

Ang pinakakilala sa mga naturang protocol ay ang Diffie-Hellman algorithm (DH), na partikular na idinisenyo upang mapadali ang key exchange. Sa protocol na ito, bawat partido ay bumubuo ng pares ng mga key (pampubliko at pribado) at ipina-broadcast ang kanilang pampublikong key. Pagkatapos, ginagamit ng bawat partido ang sarili nilang pribadong key at ang pampublikong key ng kabilang partido upang makabuo ng shared secret key. Gumagamit ang DH ng mga prinsipyo ng modular arithmetic upang matiyak na parehong partido ay magtatapos na may parehong shared secret kahit na ang bawat partido ay may access lamang sa pampublikong key ng kabilang partido.

Ang mga modernong cryptosystem batay sa elliptic curve cryptography (ECC) ay nagpapalawak ng konseptong ito gamit ang elliptic curve Diffie-Hellman (ECDH) key exchange. Ang ECDH ay gumagana nang katulad sa DH ngunit gumagamit ng mga katangian ng elliptic curves, na nagresulta sa isang mas ligtas at mahusay na sistema.

Larawan 2. Key Exchange Protocol

Larawan 2. Key Exchange Protocol

Non-interactive key exchange

Hindi tulad ng mga key exchange protocol tulad ng DH at ECDH, na interactive, na nangangailangan ng pabalik-balik na komunikasyon upang mapagpasyahan ang symmetric key, nagbibigay din ang AKC ng mga non-interactive na paraan upang maitatag ang isang shared secret key. Sa mga ganitong scheme, ang isang partido ay bumubuo ng pares ng mga key (pampubliko at pribado) at ibinabahagi ang pampublikong key sa kabilang partido. Ang pangalawang partido ay bumubuo ng isang random na symmetric key, ine-encrypt ito gamit ang natanggap na pampublikong key, at ibinabalik ito sa unang partido. Ginagamit ng unang partido ang kanilang pribadong key upang i-decrypt ang natanggap na mensahe, at sa gayon ay nakukuha ang shared symmetric key. Ang scheme na ito ay non-interactive sa aspeto na ang symmetric key ay tinutukoy ng isang partido at simpleng ligtas na ikomunika sa kabilang partido sa naka-encrypt na anyo.

Ang isang mahalagang pagsasaalang-alang sa non-interactive key exchange ay may kinalaman sa pagkakaiba ng haba sa bits sa pagitan ng symmetric key na gustong ipagpalitan ng mga partido at mga inirerekomendang laki ng mensahe sa AKC. Karaniwan, ang mga modernong symmetric key ay nasa hanay na 128-256 bits ang haba, habang ang mga asymmetric key cryptosystem tulad ng RSA ay gumagana sa mga laki ng mensahe na humigit-kumulang 1024-4096 bits ang haba. Samakatuwid, kapag gumagamit ng AKC upang maipadala ang isang symmetric key, para sa seguridad ay kailangang i-encode pa rin ito sa isang mas mahabang mensaheng 1024-4096 bits. Maaari itong makamit sa pamamagitan ng dalawang paraan:

Padding-based key exchange: Sa paraang ito, ang mas maikling (128-256 bits) symmetric key ay unang nalilikha at pagkatapos ay isang napagkasunduang reversible na padding scheme tulad ng OAEP ay ginagamit upang i-embed ito sa isang mas mahabang (1024-4096 bits) mensahe. Ang mas mahabang mensaheng ito ay ine-encrypt gamit ang AKC at ipina-broadcast bilang ciphertext. Ang tatanggap ay unang dini-decrypt ang ciphertext at pagkatapos ay inaalis ang padding upang makuha ang mas maikling symmetric key.
Key encapsulation mechanisms (KEMs): Sa KEM-based key exchange, ang isang random, mahabang (1024-4096 bits) plain text na mensahe ay unang nalilikha, mula sa kung saan maaaring makuha ang isang mas maikling (128-256 bits) symmetric key gamit ang isang napagkasunduang key derivation function (KDF). Ang mas mahabang plain text ay ine-encrypt gamit ang AKC at ipina-broadcast sa tatanggap bilang ciphertext. Dini-decode ng tatanggap ang ciphertext gamit ang kanilang pribadong key at pagkatapos ay ginagamit ang KDF upang makuha ang mas maikling (128-256 bits) symmetric key. Ang mga popular na cryptosystem tulad ng RSA, na may kakayahang direktang mag-encrypt ng data, ay maaaring gamitin upang maipatupad ang mga KEM.

Larawan 3. Key Encapsulation Mechanism

Larawan 3. Key Encapsulation Mechanism

Digital signatures gamit ang asymmetric key cryptography

Ang mga digital signature ay isa pang makapangyarihang aplikasyon ng asymmetric key cryptography. Nagbibigay sila ng authentication, integridad, at nonrepudiation na pinagana ng katotohanan na sa loob ng AKC, ang mga entidad ay nagtataglay ng natatanging mga pribadong key. Ang pangunahing ideya sa likod ng mga signature protocol ay ang mga nagpadala ng mga ligtas na mensahe ay digitally pipirmahan din ang mga mensahe gamit ang kanilang natatanging pribadong key. Ang tatanggap ay mag-ve-verify ng digital signature gamit ang pampublikong key ng nagpadala. Sa loob ng AKC, ang mga digital signature ay maaaring maipatupad sa pamamagitan ng paggamit ng mga algorithm na espesyal na idinisenyo para sa layuning iyon o sa pamamagitan ng paggamit ng mga generic na cryptosystem.

Larawan 4. Digital signatures gamit ang asymmetric key cryptography

Larawan 4. Digital signatures gamit ang asymmetric key cryptography

Mga dedicated na digital signature algorithm

Sa kasalukuyan, ang US Federal Information Processing Standard (FIPS) para sa mga digital signature ay isang dedicated na scheme na simpleng pinamagatang Digital Signature Algorithm (DSA). Medyo katulad sa Diffie-Hellman protocol, ginagamit ng DSA ang algebraic na katangian ng modular exponential at multiplicative inverses para sa pagbuo at pag-verify ng signature.

Ang elliptic curve digital signature algorithm (ECDSA) ay isang ECC variant ng DSA, na nagbibigay ng parehong functionality ngunit may mas maikling mga key. Nagresulta ito sa pinahusay na kahusayan, na ginagawa itong popular na pagpipilian para sa mga sistema na may limitasyon sa resources.

Ang parehong DSA at ECDSA ay ilalalarawan nang mas detalyado sa ibang pagkakataon.

Mga digital signature scheme gamit ang mga generic na cryptosystem

Bukod sa mga dedicated na algorithm, ang mga digital signature ay maaari ring mabuo gamit ang mga generic na asymmetric cryptosystem, tulad ng RSA.

Ang RSA, na tatalakayin nang detalyado sa susunod na seksyon, ay gumagamit din ng modular multiplicative inverses at modular exponentiation bilang mga pundamental na operasyon ngunit pinagsama ang mga ito sa ibang pagkakasunud-sunod kaysa sa DSA. Sa RSA, ang signer ay karaniwang gumagawa ng hash ng mensahe at pagkatapos ay ine-encrypt ang hash gamit ang kanilang pribadong key, na lumilikha ng digital signature. Ang sinumang partido ay maaaring i-verify ang signature na ito sa pamamagitan ng pag-decrypt nito gamit ang pampublikong key ng signer at pagkukumpara nito sa hashed na mensahe.

Mga aplikasyon ng asymmetric key cryptography

Ang asymmetric key cryptography ay laganap sa mga modernong aplikasyon ng digital na teknolohiya. Ang mga pangunahing functionality ng AKC na inilalarawan sa itaas ay bumubuo ng mga building block ng maraming higher-level na application protocol, kabilang ang:

Komunikasyon sa internet: Ang ligtas na komunikasyon sa internet, tulad ng HTTPS, ay mabigat na umaasa sa asymmetric key cryptography. Ang Transport Layer Security (TLS) at ang nauna nitong Secure Sockets Layer (SSL), ay gumagamit ng asymmetric key cryptography sa panahon ng paunang proseso ng handshake upang maitatag ang isang symmetric key, na ginagamit sa natitirang bahagi ng session ng komunikasyon.
Authentication: Ang asymmetric key cryptography ay ginagamit upang lumikha ng mga digital signature, na nagpapahintulot sa isang entidad na i-authenticate ang isang digital na dokumento o mensahe na nagmula sa isang partikular na nagpadala. Ginagamit ito sa maraming sitwasyon, mula sa pag-verify ng mga software update hanggang sa mga legal na binding na digital na kontrata.
Email encryption: Ang mga email encryption protocol tulad ng PGP (Pretty Good Privacy) at ang open-source na alternatibo nitong GPG (GNU Privacy Guard) ay gumagamit ng asymmetric key cryptography upang matiyak na ang nilalaman ng email ay mababasa lamang ng nilayong tatanggap.
Secure shell (SSH): Ang SSH ay isang protocol para sa ligtas na remote login at iba pang ligtas na serbisyo ng network sa pamamagitan ng isang hindi ligtas na network. Gumagamit ito ng asymmetric key cryptography upang ma-authenticate ang server sa client at, opsyonal, ang client sa server.
VPN (virtual private network): Ginagamit ang asymmetric key encryption upang maitatag ang mga ligtas na koneksyon sa mga VPN, na tinitiyak ang ligtas na komunikasyon sa pamamagitan ng mga pampublikong network.
Blockchain at mga cryptocurrency: Ang mga teknolohiya ng blockchain, kabilang ang Bitcoin at Ethereum, ay gumagamit ng asymmetric key cryptography. Halimbawa, ang pagmamay-ari ng Bitcoin ay itinatag sa pamamagitan ng mga digital signature gamit ang asymmetric key cryptography.
Mga certificate authority: Ang asymmetric key cryptography ay ginagamit ng mga certificate authority (CA) upang mag-issue at pumirma ng mga digital na sertipiko, na ginagamit sa TLS communication, code signing, email encryption, at iba pa. Ang isang digital na sertipiko ay nagbubuklod ng isang pampublikong key sa isang partikular na entidad (halimbawa, isang tao o server).

Larawan 5. Pag-issue at pagpirma ng mga digital na sertipiko gamit ang asymmetric key cryptography

Larawan 5. Pag-issue at pagpirma ng mga digital na sertipiko gamit ang asymmetric key cryptography

Seguridad ng asymmetric key cryptography

Ilang cryptographic na konsepto ang nagsasama upang paganahin ang ligtas na asymmetric key cryptography, kabilang ang:

Lihimang pribadong key: Ang pinakabasikong kinakailangan sa seguridad ng AKC ay ang pribadong key ay nananatiling lihim. Gayunpaman, dahil ang pribadong key ay dapat na mathematically na naka-link sa pampublikong key, ang pagiging lihim ng pribadong key ay nangangailangan din na hindi maisagawa sa computational ang pagkuha ng pribadong key mula sa kaalaman ng pampublikong key. Ang mga scheme ng pagbuo ng key sa loob ng AKC ay umaasa sa mga computationally mahirap na mathematical na problema upang mapadali ang kinakailangang ito.

Trapdoor functionality: Sa AKC, ang mga operasyon ng encryption at decryption ay gumagamit ng iba't ibang complementary na mga key mula sa isang key pair. Ang Ciphertext na nalikhang sa pamamagitan ng encryption gamit ang isa sa mga key (halimbawa ang pampublikong key) ay dapat na hindi maintindihan ng mga ikatlong partido habang madaling ma-decrypt ng may hawak ng complementary na key (sa kasong ito ang pribadong key). Sa madaling salita, ang encryption ay dapat na kahawig ng isang trapdoor one-way function upang ang mga ikatlong partido ay hindi maka-invert ng operasyon at mabawi ang plain text ngunit ang pribadong key ay nagbibigay ng lihim na trapdoor na nagbibigay-daan sa madaling pag-invert. Ang mga popular na AKC algorithm ay gumagamit ng modular exponentiation upang maitatag ang gawi ng trapdoor one-way function.

Randomness: Ang proseso ng pagbuo ng key ay dapat ding gumamit ng randomness upang matiyak na ang mga key ay hindi mahuhulaan, dahil ang anumang pattern o predictability sa pagbuo ng key ay maaaring mapagsamantalahan ng isang attacker. Ang randomness ay ginagamit din para sa padding sa panahon ng encryption upang makabuo ng semantically secure na mga ciphertext at sa loob ng mga digital signature scheme upang makagawa ng natatanging mga signature kahit na ang parehong mensahe ay pinirmahan nang maraming beses. Para sa kadahilanang ito, ang paggamit ng mga malakas na random number generator ay isang mahalagang bahagi ng AKC.

Malaking laki ng key: Tulad ng kaso ng SKC, ang malalaking laki ng key ay nagbibigay ng proteksyon laban sa brute force attack. Gayunpaman, dahil ang malalaking laki ng key ay nagpapataas din ng computational na gastos ng proseso ng encryption at decryption, ang isang optimal na solusyon ay kailangang balansehin ang mga pagsasaalang-alang sa seguridad at kahusayan. Ang sumusunod na talahanayan ay nagpapakita ng mga tipikal na laki ng key para sa iba't ibang asymmetric key cryptography protocol at aplikasyon:

Protocol	Mga Tipikal na Laki ng Key (sa bits)	Aplikasyon
RSA	1024 (deprecated), 2048, 3072, 4096	Encryption, digital signatures
DSA	1024 (deprecated), 2048, 3072	Digital signatures
DH	2048, 3072, 4096	Key exchange
ECDH	224, 256, 384, 521	Key exchange
ECDSA	224, 256, 384, 521	Digital signatures

Public key infrastructure: Sa AKC, ang mga pribadong key ay dapat na panatilihing lihim ng mga may-ari habang ang mga pampublikong key ay ibinabahagi. Kailangan ng isang ligtas na mekanismo upang pamahalaan at ipamahagi ang mga pampublikong key na ito sa pagitan ng mga gumagamit. Ang Public key infrastructure (PKI) ay nagbibigay ng isang paraan upang gawin ito gamit ang mga digital na sertipiko. Ang isang digital na sertipiko ay nagbibigay ng patunay ng pagkakakilanlan ng may-ari ng pampublikong key at inilalabas ng isang pinagkakatiwalaang awtoridad tulad ng isang certificate authority (na bahagi ng PKI). Kaya, ang PKI ay gumaganap ng mahalagang bahagi sa seguridad ng modernong aplikasyon gamit ang AKC sa pamamagitan ng pagpapagana ng large-scale na pamamahala ng key (sa pamamagitan ng paglikha, pamamahala, pamamahagi at pagbawi ng mga digital na sertipiko).

Mga panganib sa seguridad ng asymmetric key cryptography

Tulad ng nakasaad sa talahanayan sa itaas, ang mga modernong asymmetric key algorithm tulad ng RSA ay karaniwang gumagamit ng mas malalaking laki ng key kaysa sa mga karaniwang ginagamit na symmetric key counterpart tulad ng AES-128. Kahit ang mga ECC-based na protocol (ECDH at ECDSA) na may mas maliliit na laki ng key ay gumagamit ng minimum na hindi bababa sa 224 bits para sa mga key. Ito naman ay nagpapahiwatig na ang isang brute force attack na kinabibilangan ng exhaustive search ng private key space upang matukoy ang tamang key ay computationally intractable sa nakikitang hinaharap. Nananatili itong totoo kahit na ang mga quantum computer ay ilalagay para sa gawaing ito. Samakatuwid, ang mga pag-atake laban sa AKC ay karaniwang nakatuon sa pagsasamantala ng iba pang posibleng kahinaan ng mga partikular na cryptosystem. Ilang well-documented na attack mode ang nagta-target:

Kahinaan ng algorithm sa pamamagitan ng paggamit ng mga sopistikadong mathematical at computational na paraan upang sirain ang mga hardness assumption na ginamit upang bumuo ng mga asymmetric key algorithm. Halimbawa, ang seguridad ng RSA ay nakabase sa kahirapan ng pag-factor ng malalaking prime number, at ang mga kamakailang computational na pagsulong ay nagpahintulot ng matagumpay na pag-factor ng 829-bit na RSA key. Samakatuwid, ang 1024-bit na RSA ay kasalukuyang deprecated. Tulad ng tatalakayin sa ibang pagkakataon, ang pangunahing panganib na inilalahad ng mga quantum computer sa AKC ay napapabilang din sa kategoryang ito.
Hindi perpektong randomness, na maaaring magdulot ng kahinaan sa proseso ng pagbuo ng key. Halimbawa, kung ang random number generator na ginagamit upang lumikha ng mga key ay may depekto at bumubuo ng mga key na hindi tunay na random, maaaring matukoy ng isang attacker ang mga key.
Mga depekto sa implementasyon tulad ng mga pagkakamali sa implementasyon ng mga cryptographic algorithm na hindi sinasadyang nagbubunyag ng impormasyon tungkol sa mga key. Halimbawa, ang maling padding ay maaaring potensyal na magbunyag ng mga detalye tungkol sa mga key.
Mga side channel na tumutukoy sa pagtagas ng impormasyon mula sa pisikal na sistema na gumaganap ng cryptography. Ang ganitong mga pagtagas ay maaaring nasa anyo ng impormasyon sa timing, pagkonsumo ng kuryente, o kahit tunog, na maaaring mapagsamantalahan sa tinatawag na side-channel attack. Halimbawa, ang pagsusuri kung gaano katagal ang mga cryptographic na operasyon na isasagawa ay maaaring magbunyag ng bilang ng mga '1' sa isang binary key. Ang tila walang masamang pagtagas na ito ay makabuluhang nagpapaliit ng search space, na nagbubunyag ng mga potensyal na solusyon sa mga problemang sa una ay tila hindi malulutas.
Key exchange sa pamamagitan ng pagharang sa mga key habang ito ay ipinalpalitan, tulad ng sa loob ng isang man-in-the-middle attack (MITM). Ang DH protocol ay madaling atakihin ng MITM kung walang karagdagang hakbang ng authentication.
Key storage sa pamamagitan ng paglalayon na magnakaw ng mga key mula sa hindi ligtas na storage. Kasama dito ang mga pisikal na pag-atake tulad ng manipulasyon o pagnanakaw ng mga device ng storage.

Ang pag-secure ng mga asymmetric key cryptosystem laban sa iba't ibang pag-atake na posible ay samakatuwid isang makabuluhang gawain na kinabibilangan ng mga mathematical, hardware, software, logistical, at legal na pagsasaalang-alang.

RSA

Ang RSA (Rivest-Shamir-Adleman) algorithm ay isa sa mga unang public key cryptosystem at malawakang ginagamit para sa ligtas na pagpapadala ng data. Isa itong versatile na cryptosystem dahil nagbibigay ito ng mga kinakailangang operasyon upang paganahin ang encryption, decryption, mga digital signature, at key exchange sa loob ng isang karaniwang balangkas.

Sa seksyong ito, ilalarawan natin ang asymmetric key cryptography (AKC) gamit ang RSA sa pamamagitan ng mga simpleng halimbawa.

Gagamitin natin ang karaniwang senaryo ng dalawang partido, si Alice at Bob, na gustong makipag-usap nang ligtas gamit ang AKC.

Ang RSA algorithm

Ang pangunahing RSA algorithm ay kinabibilangan ng apat na operasyon: key generation, key distribution, encryption, at decryption:

Key generation:

Ang mga pampubliko at pribadong key ay nalilikha batay sa mga mathematical na prinsipyo tungkol sa mga prime number, kung saan ang pagkalkula ng mga ito ay madali, ngunit ang kabaligtaran ay mahirap.

Ito ang ating gagamitin:
- Pampublikong key: $(e, n)$
- Pribadong key: $(d, n)$
Tandaan na ang $n$ ay karaniwan sa parehong pampubliko at pribadong key, at kilala bilang modulus. Kakailanganin nating gamitin ito sa ibang pagkakataon.

Mathematical na detalye

Pumili ng dalawang natatanging prime number, $p$ $p$ at $q$ $q$ .
- pinili nang random (para sa seguridad).
- Dapat silang magkatulad sa magnitude, ngunit mag-iiba ng ilang digit sa haba, upang gawing mas mahirap ang pag-factor.
- Ang mga prime number ay maaaring mahusay na mapili gamit ang isang primality test.
Kalkulahin ang $n = p*q$ $n = p * q$ .
- Ang $n$ ay ang modulus para sa parehong pampubliko at pribadong key.
Kalkulahin ang totient $φ$ $(n) = (p-1)*(q-1)$ $(n) = (p - 1) * (q - 1)$ .
- Ang totient ay dapat na panatilihing lihim at karaniwang itinatapon pagkatapos ng key generation.
Pumili ng integer na $e$ $e$ upang $1 < e <$ $1 < e <$ $φ$ $(n)$ $(n)$ at $gcd$ $(e,$ $(e,$ $φ$ $(n)) = 1$ $(n)) = 1$ .
- ibig sabihin, ang $e$ at $φ$ $(n)$ ay dapat na coprime.
- Ang numerong $e$ na ito ay bumubuo ng pampublikong key exponent at karaniwang pinipili bilang isang maliit na numero para sa computational na kahusayan.
- Ang prime number na $65537 = 2^{16} + 1$ ay madalas na ginagamit.
- Kalkulahin ang $d$ $d$ upang masiyahan ang congruence relation na $d*e ≡ 1 ($ $d * e \equiv 1 ($ $mod$ $φ$ $(n))$ $(n))$ .
  - Ibig sabihin, ang $d$ ay ang multiplicative inverse ng $e$ modulo $φ$ $(n)$ .
  - Ito ay mas mahusay na kinakalkula gamit ang extended Euclidean algorithm.
  - Ang numerong $d$ na ito ay ang pribadong key exponent.
Ang pampublikong key ay binubuo ng $(e, n)$ , at ang pribadong key ay $(d, n)$ .

Key distribution:
- Ang pampublikong key $(e, n)$ ay ginagawang pampubliko para sa mga gustong magpadala ng mensahe
- Ang pribadong key $(d, n)$ ay pinapanatiling lihim.
Encryption:
- Gustong magpadala ni Alice ng mensaheng $M$ kay Bob. Sa kasong ito ay isang simpleng integer
- Ginagamit ni Alice ang pampublikong key ni Bob $(e, n)$ upang i-encrypt ang mensahe bilang ciphertext $C$
Mathematical na detalye
- Ang $M$ ay isang integer na $0 ≤ M < n$ .
- $C ≡ M^e (mod n)$ , kung saan ang $C$ ay ang ciphertext.
Decryption:
- Natanggap ni Bob ang ciphertext $C$
- Ginagamit ni Bob ang kanyang pribadong key $(d, n)$ upang i-decrypt ang mensahe pabalik sa mensaheng $M$
Mathematical na detalye
- $M ≡ C^d (mod n)$ .

Ito ang pangunahing balangkas ng RSA. Sa praktiko, mas sopistikadong mga padding scheme ang inilalapat sa plain text na $M$ bago ang encryption upang matiyak na ang mga pantay na plain text ay nagresulta sa iba't ibang ciphertext. Pinipigilan nito ang isang hanay ng mga posibleng pag-atake laban sa mga naive na implementasyon ng RSA at nagpapagana ng semantic security.

Ilustrasyon ng RSA sa Python

Sa mga sumusunod na code cell, ipinapakita natin ang isang simpleng halimbawa ng RSA algorithm gamit ang maliliit na integer, at pagkatapos ay nagpapakita ng praktikal na key distribution at digital signature na mga aplikasyon gamit ang mga Python library na nagpapatupad ng RSA.

tala

Tandaan: Sa seksyong ito, ipapakita natin ang mga kalkulasyong matematikal nang detalyado bilang bahagi ng Python code

Paglikha ng RSA key

Sundan natin ang isang simpleng halimbawa ng RSA algorithm gamit ang maliliit na prime na numero.

Kakailanganin nating makalkula ang greatest common divisor ng dalawang integer, dahil kailangan ito para masuri kung ang dalawang integer ay coprime.

Magpapaliwanag tayo ng isang simpleng paraan para kalkulahin ito, ngunit mas mahusay para sa malalaking integer ang paggamit ng math.gcd na Python function.

# Added by doQumentation — required packages for this notebook
!pip install -q cryptography

import math

# Example function to compute the gcd (greatest common divisor)
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

# let's calculate some examples using algorithm
n1 = gcd(50, 10)
n2 = gcd(99, 33)
n3 = gcd(59, 9)

# do the same with the python library call

m1 = math.gcd(50, 10)
m2 = math.gcd(99, 33)
m3 = math.gcd(59, 9)

# Confirm they are the same
assert n1 == m1
assert n2 == m2
assert n3 == m3

# They are - print out the values for explanation
print("gcd(50,10) =", m1)
print("gcd(99,33) =", m2)
print("gcd(59,9) =", m3)

Ang unang yugto ng RSA workflow ay ang paglikha ng key. Nagsisimula ito sa pagpili ng dalawang prime na numero, na dapat itago ng entity na gumagawa ng mga key.

# Choosing two prime numbers and keep them secret
p = 13
q = 19
print("The secret prime numbers p and q are:", p, q)

Susunod, kinakalkula ang modulus $n$ , na simpleng produkto ng dalawang piniling prime. Ang modulus na ito ay ilalathala bilang bahagi ng public key.

# Calculate n which is the modulus for both the public and private keys
n = p * q
print("modulus n (p*q)=", n)

Ang Euler totient function na $\varphi(n)$ ay kinakalkula susunod, dahil kailangan ito para sa modular multiplicative inverse na operasyon na ginagamit para matukoy ang mga key sa RSA. Ang $phi$ ay itinatago rin nang lihim at karaniwang itinatapon pagkatapos ng key generation.

# Compute Euler's totient function, φ(n) and keep it secret
phi = (p - 1) * (q - 1)
print("The secret Euler's function (totient) [phi(n)]:", phi)

Handa na tayo ngayon na kalkulahin ang mga public at private key. Sa RSA, ang bawat isa sa mga ito ay tinukoy ng tuple ng dalawang integer. Ang unang entry sa bawat tuple ay isang natatanging integer, at ang pangalawang entry ay ang modulus $n$ na karaniwan sa parehong key.

Ang unang entry sa public key ay maaaring maging anumang integer na mas malaki sa 1 na coprime sa $phi$ . Ang dalawang integer ay coprime kung ang kanilang greatest common divisor ay 1. Kaya ginagamit natin ang math.gcd function para mahanap ang integer $e$ na coprime sa $phi$ .

# Choose an integer e such that e and φ(n) are coprime
e = 2
while e < phi:
    if math.gcd(e, phi) == 1:
        break
    else:
        e += 1
print("Public Key (e):", e)

Ang private key ay nangangailangan ng integer $d$ , na siyang multiplicative inverse ng $e$ modulo $phi$ ; ibig sabihin, nasasabay ito sa congruency relation na $d*e\equiv 1 \pmod{\varphi(n)}$ . Para sa simpleng ilustrasyong ito na gumagamit ng maliliit na integer, maaari tayong mag-loop sa mga positibong integer para mahanap ang angkop na $d$ . Sa mga realitibong setting, ang computationally efficient na extended Euclidean algorithm ang ginagamit para sa layuning ito.

# Compute a value for d such that (d * e) % φ(n) = 1
d = 1
while True:
    if (d * e) % phi == 1:
        break
    else:
        d += 1
print("Private Key (d):", d)

Binubuo na natin ngayon ang mga tuple $(e, n), (d, n)$ , na nagbibigay ng public at private key ayon sa pagkakasunod. Ang public key ay ilalathala, habang ang private key ay itinatago nang lihim.

# Public and Private Key pair
public = (e, n)
private = (d, n)

print(f"The Public key is {public} and Private Key is {private}")

Ang encryption at decryption sa RSA ay gumagamit ng modular exponentiation operation. Bukod dito, ang mga public at private key ay magkakomplemento sa lawak na ang alinman sa mga ito ay maaaring gamitin para i-encrypt ang isang mensahe na maaaring i-decrypt ng isa.

Dito ipinapakita natin ang kaso kung saan ang public key $(e,n)$ ay ginagamit para sa encryption at ang private key $(d, n)$ ay ginagamit para sa decryption sa pamamagitan ng pagtukoy ng Python function para sa bawat operasyon.

Pagkatapos ay ine-encrypt at dine-decrypt natin ang isang integer na mensahe $msg$ .

# Encryption function
def encrypt(plain_text):
    return (plain_text**e) % n

# Decryption function
def decrypt(cipher_text):
    return (cipher_text**d) % n

# Simple message to encode
msg = 9

# encrypt then decrypt
enc_msg = encrypt(msg)
dec_msg = decrypt(enc_msg)

print("Original Message:", msg)
print("Encrypted Message:", enc_msg)
print("Decrypted Message:", dec_msg)

Habang ang maliliit na integer na ginamit sa itaas ay kapaki-pakinabang para madaling ibalangkas ang mga pangunahing ideya sa RSA algorithm, sa mga tunay na aplikasyon ang RSA ay nangangailangan ng paggamit ng napakalaking integer. Halimbawa, ang 2048-bit RSA ay gumagamit ng modulus $n$ na 2048 bits ang haba, na ang katumbas na decimal integer ay humigit-kumulang 10 $^616$ . Ang mga tunay na napakalaking numerong ito ay kinakailangan para sa praktikal na seguridad ng RSA.

Palitan ng symmetric key gamit ang RSA

Gaya ng tinalakay nang mas maaga, ang AKC ay nagbibigay-daan sa dalawang partidong gustong makipag-communicate na ligtas na magtatag ng isang shared secret, na maaaring gamitin, halimbawa, bilang secret key para sa kasunod na symmetric encryption ng bulk na plain text.

Isaalang-alang natin ang sumusunod na sitwasyon. Gusto ni Alice at Bob na gumamit ng SKC para mag-encrypt at mag-decrypt ng mga mensahe. Gayunpaman, bago masimula ang prosesong ito, kailangan nilang magkasundo sa isang karaniwang secret key. Isang opsyon ay para sa isang partido — sabihin nating si Alice — na lumikha ng secret key at pagkatapos ay ligtas na ipadala ito kay Bob. Para makamit ang ligtas na paglilipat na ito, nagpasya si Alice na gamitin ang RSA bilang key encapsulation mechanism (KEM).

Kabilang sa prosesong ito ang mga sumusunod na hakbang:

Una, lumilikha si Alice ng isang random na symmetric key, na balak niyang ibahagi kay Bob.
Pagkatapos, gumagawa si Bob ng asymmetric key pair at ginagawa ang kanyang public key available sa isang angkop na channel.
Susunod, ginagamit ni Alice ang public key ni Bob para i-encrypt ang symmetric key, kaya ikinakapsul ito sa isang ciphertext.
Pagkatapos, ibinabahagi ni Alice ang ciphertext sa isang maaasahang ngunit hindi naman kailangang ligtas na channel.
Sa wakas, tinatanggap ni Bob ang ciphertext at dine-decrypt ito gamit ang kanyang private key. Mayroon na siyang access sa symmetric key na nilikha ni Alice.

Figure 1. Symmetric key exchange with RSA

Figure 1. Palitan ng symmetric key gamit ang RSA

Halimbawa ng padding-based na key exchange sa Python

Isang praktikal na workflow na gumagamit ng RSA para sa padding-based na non-interactive key exchange ay ipinapakita ngayon gamit ang cryptography na Python library.

I-import ang mga kinakailangang module mula sa cryptography na Python library. Kung kinakailangan, ang library na ito ay maaaring i-install gamit ang command na pip install cryptography.

Pagkatapos, lumilikha si Alice ng random na secret key, na balak niyang ipadala kay Bob.

# pip install cryptography
from cryptography.hazmat.primitives import serialization
from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.fernet import Fernet
from cryptography.hazmat.primitives import hashes

symmetric_key = Fernet.generate_key()
print(f"\nSymmetric key generated by Alice: {symmetric_key}")

Gamit ang rsa module mula sa cryptography library, gumagawa si Bob ng key pair at pagkatapos ay ibinabahagi ang kanyang public key. Maaaring mapigilan ng sinuman ang public key at mabasa ang mga public number $(e,n)$ na bumubuo sa key.

# Bob generates a 2048-bit RSA key pair
bob_private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
bob_public_key = bob_private_key.public_key()
print(f"Public key broadcast by Bob: {bob_public_key}")
print(f"\nPublic numbers in Bobs' public key: {bob_public_key.public_numbers()}")

Sa puntong ito, ipinapalagay nating natanggap ni Alice ang public key na ibinahagi ni Bob. Ang symmetric_key ni Alice sa itaas ay maaari nang i-encrypt gamit ang public key ni Bob para makagawa ng ciphertext. Sa isang realitibong setting, gagamit din si Alice ng karagdagang mga paraan ng padding tulad ng OAEP para matiyak ang semantic security para sa kanyang mga komunikasyon kay Bob.

# Encryption
ciphertext = bob_public_key.encrypt(
    symmetric_key,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("Ciphertext:", ciphertext)

Ibinabahagi ni Alice ang ciphertext sa isang bukas na channel, tiwala na si Bob lamang na may kaukulang private key ang makakapag-decrypt nito. Ipinapalagay nating natanggap ni Bob ang ciphertext at maaari na itong i-decrypt gamit ang kanyang kumpidensyal na private key.

# Bob decrypts ciphertext to access the symmetric key
decrypted_symmetric_key = bob_private_key.decrypt(
    ciphertext,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("Decrypted key:", decrypted_symmetric_key)
assert decrypted_symmetric_key == symmetric_key

Sa puntong ito, parehong si Alice at Bob ay may access na sa secret symmetric key, na maaari nilang gamitin para sa mga aplikasyon ng SKC.

Pagsimula ng Key Encapsulation Mechanism gamit ang RSA sa Python

Sa sumusunod na workflow, ipinapakita natin ang paggamit ng RSA para gayahin ang isang Key Encapsulation Mechanism (KEM) kung saan isang sapat na mahaba random na secret na mensahe ay ligtas na ipinagpapalit at kasunod na kino-convert sa isang shared secret ng angkop na haba gamit ang isang KDF.

Muli, gusto ni Alice at Bob na magtatag ng isang shared secret nang hindi nagta-transact nang direkta, at si Alice ang partido na nagpapasya kung aling secret ang gagamitin.

Nagsisimula tayo sa pag-import ng ilang kinakailangang Python library.

Pagkatapos, gumagawa si Bob ng kanyang RSA key pair at ibinabahagi ang kanyang public key.

from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.hazmat.primitives.kdf.hkdf import HKDF
from cryptography.hazmat.primitives import hashes
from os import urandom

# Bob's RSA key pair
private_key_Bob = rsa.generate_private_key(public_exponent=65537, key_size=2048)
public_key_Bob = private_key_Bob.public_key()

print("Bob's private and public keys created")

Unang gumagawa si Alice ng isang mahabang random na secret mula sa kung saan sa kalaunan ay matatamo ang shared secret. Sa isang purong KEM, ang mahabang secret ay magiging isang random na elemento mula sa algebraic na istruktura na pinagbabatayan ng cryptosystem. Sa kaso ng 2048-bit RSA, ito ay magiging isang random na integer na modulo ng 2048-bit RSA modulus. Dahil ang isang purong KEM ay hindi nangangailangan ng karagdagang padding ngunit sa halimbawang ito ay gina-gaya lamang natin ang isang KEM gamit ang RSA at ang cryptography library ay nangangailangan ng paggamit ng padding kapag nag-e-encrypt gamit ang RSA. Kaya gagamit tayo ng medyo mas maikling mahabang secret na gayunpaman ay mas mahaba pa rin kaysa sa isang karaniwang 256-bit AES key.

Alice_long_secret = urandom(160)  # A 160 byte or 1280 bit random message
print("Alice's secret created")

Susunod, ine-encrypt ni Alice ang mahabang secret gamit ang public key ni Bob at ang naka-encrypt na secret ay ipinagpapalit kay Bob.

Alice_encrypted_secret = public_key_Bob.encrypt(
    Alice_long_secret,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)
print("Alice's secret encrypted")

Dine-decrypt ni Bob ang naka-encrypt na secret na natanggap mula kay Alice gamit ang kanyang private key.

Bob_decrypted_secret = private_key_Bob.decrypt(
    Alice_encrypted_secret,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

assert Alice_long_secret == Bob_decrypted_secret, "Secrets do not match!"

# if we get here they match
print("Secrets match")

Sa wakas, parehong si Alice at Bob ay magkahiwalay na nag-aaplay ng napagkasunduang Key Derivation Function (KDF) sa mahabang secret para makuha ang symmetric key.

Tandaan na ang proseso ay kinabibilangan ng isang hashing protocol at ang paggamit ng isang random na salt na tinitiyak ang pagiging natatangi at hindi mahulaan ng shared symmetric key sakaling ang mahabang secret ay muling gamitin (hindi inirerekomenda). Gayunpaman ang salt mismo ay hindi kailangang maging lihim at kapag random itong nagawa, sabihin nating ni Alice sa halimbawang ito, maaari itong ibahagi kay Bob kasabay ng naka-encrypt na mahabang secret.

Ipinapalagay nating parehong si Alice at Bob ay may access sa parehong random na salt.

def key_derivation_function(secret, salt):
    hkdf = HKDF(
        algorithm=hashes.SHA256(),
        length=32,  # Desired key length
        salt=salt,
        info=None,
        backend=None,
    )
    return hkdf.derive(secret)

common_salt = urandom(16)  # Random salt accessible to both Alice and Bob

symmetric_key_Alice = key_derivation_function(Alice_long_secret, common_salt)
symmetric_key_Bob = key_derivation_function(Bob_decrypted_secret, common_salt)

assert symmetric_key_Alice == symmetric_key_Bob, "Derived keys do not match!"
print(
    f"A symmetric key of length {len(symmetric_key_Alice)*8} bits was successfully derived by both Alice and Bob!"
)

Mga digital signature gamit ang RSA

Palawakin na natin ngayon ang sitwasyon ng kumpidensyal na komunikasyon sa pagitan ni Alice at Bob para isama rin ang validation sa tulong ng isang digital signature.

Gaya ng dati, lihim na magpapadala si Alice ng mensahe na naglalaman ng symmetric key kay Bob, ngunit maglalagay din siya ng digital signature sa mensahe para mapatunayan ni Bob, sa pagtanggap ng mensahe, na si Alice ang nagpadala nito at na ang nilalaman ng mensahe ay hindi binago sa panahon ng pagpapadala.

Sa pangkalahatan, kanais-nais na mapagana ang validation nang hindi nakompromiso ang kumpidensyalidad kung saan ang anumang interesadong partido ay may kakayahang i-verify ang integridad, pagiging tunay, at magtayo ng non-repudiation kaugnay ng isang ibinigay na komunikasyon, kahit na ang partidong iyon ay walang access sa aktwal na plain text na mensahe.

Isasaalang-alang natin ang pangkalahatang setting na ito na kinabibilangan ng mga sumusunod na hakbang:

Una, parehong si Bob at Alice ay ginagawang available ang kanilang mga public key sa isang bukas na channel.
Pagkatapos, ine-encrypt ni Alice ang plain text gamit ang public key ni Bob, na lumilikha ng isang ciphertext.
Susunod, gumagawa si Alice ng hash ng ciphertext gamit ang isang hash function at dagdag na ine-encrypt ang nagresultang na-hash na ciphertext gamit ang kanyang private key. Ang naka-encrypt na hash na ito ay ang signature.
Pagkatapos, ipinapadala ni Alice ang parehong ciphertext at signature sa isang bukas na channel.
Pagkatapos, ginagamit ni Bob ang public key ni Alice para i-decrypt ang signature, inilalantad ang na-hash na ciphertext.
Susunod, dahil mayroon ding access si Bob sa ciphertext mismo, ginagamit niya ang parehong hash function na ginamit ni Alice para muling lumikha ng pangalawang instance ng na-hash na ciphertext. Kung ang huli ay tumutugma sa nakuha sa pamamagitan ng pag-decrypt ng signature ni Alice, ang mensahe ay na-validate, kahit na ang ciphertext mismo ay hindi pa na-decrypt.
Sa wakas, si Bob, na na-validate na ang mensahe, ay dine-decrypt ang ciphertext gamit ang kanyang sariling private key.

Figure 2. Digital signatures with RSA

Figure 2. Mga digital signature gamit ang RSA

Ang workflow para sa isang digital signature ay ipinapakita sa susunod.

Muli naming ini-import ang ilang kapaki-pakinabang na module mula sa cryptography library. Gaya ng dati, balak ni Alice na ligtas na magpadala ng isang symmetric key kay Bob, ngunit nais din niyang digital na lagdaan ito. Sa kasong ito, kailangan natin ng mga public key para sa parehong si Alice at Bob. Samakatuwid, ang unang hakbang ay para sa parehong si Alice at Bob na lumikha ng kanilang sariling key pair gamit ang RSA at ibahagi ang kanilang sariling public key sa lahat.

from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import padding, rsa
from cryptography.hazmat.primitives.asymmetric.utils import Prehashed

# Generate keys for Bob
bob_private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
bob_public_key = bob_private_key.public_key()

# Generate keys for Alice
alice_private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
alice_public_key = alice_private_key.public_key()

print("Private and Public keys generated for Bob and Alice.")

Sa susunod na hakbang, gaya ng dati, ginagamit ni Alice ang public key ni Bob para i-encrypt ang symmetric key at inihahanda ang ciphertext.

# Alice encrypts the message using Bob's public key
ciphertext = bob_public_key.encrypt(
    symmetric_key,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("ciphertext of symmetric key: ", ciphertext)

Sa yugtong ito, sa halip na ibahagi lamang ang ciphertext, balak ni Alice na mag-attach ng digital signature dito para mapatunayan niya kay Bob na siya ang nagpadala ng mensahe. Ginagawa ito sa dalawang hakbang:

Lumikha ng hash ng ciphertext gamit ang isang hashing algorithm.
I-encrypt ang hash gamit ang private key ni Alice, na katumbas ng isang signature.

# Alice signs the ciphertext using her private key
digest = hashes.Hash(hashes.SHA256())
digest.update(ciphertext)
hash_to_sign = digest.finalize()

signature = alice_private_key.sign(
    hash_to_sign,
    padding.PSS(mgf=padding.MGF1(hashes.SHA256()), salt_length=padding.PSS.MAX_LENGTH),
    Prehashed(hashes.SHA256()),
)

print("signature: ", signature)

Ibinahagi ni Alice ang ciphertext at signature sa isang network para matanggap ni Bob ang pareho sa kanila.

# Bob receives the ciphertext and signature
received_ciphertext = ciphertext
received_signature = signature

# Send signature and ciphertext here
print("Sending ciphertext and signature.....")

Sa panig ni Bob, ang unang gawain ay i-verify ang integridad at pagiging tunay ng ciphertext. Para gawin ito, gumagawa si Bob ng hash ng natanggap na ciphertext gamit ang parehong hashing algorithm na ginamit ni Alice.

# Bob creates a hash of the ciphertext using the same algorithm used by Alice
digest = hashes.Hash(hashes.SHA256())
digest.update(received_ciphertext)
hash_to_verify = digest.finalize()

print("hash to verify: ", hash_to_verify)

Pagkatapos, dine-decrypt ni Bob ang natanggap na signature gamit ang public key ni Alice. Dahil ginamit ni Alice ang kanyang private key para gumawa ng signature, nagagawa ni Bob na i-decrypt ito gamit ang public key ni Alice. Ang na-decrypt na signature ay wala nang iba kundi isang hash ng ciphertext na ginawa sa panig ni Alice. Kung ang hash na ginawa ni Bob ay tumutugma sa na-decrypt na signature, napatunayan ni Bob na ang ciphertext na natanggap niya ay hindi binago at si Alice ang naglagda ng ciphertext.

Sa Python code sa ibaba, ang mga operasyong ito ay pinagsama sa isang kapaki-pakinabang na utility function na tinatawag na verify na ibinibigay ng isang object na nauugnay sa public key ni Alice.

from cryptography.exceptions import InvalidSignature

def is_signature_valid(public_key, signature, data_hash):
    try:
        public_key.verify(
            signature,
            data_hash,
            padding.PSS(
                mgf=padding.MGF1(hashes.SHA256()), salt_length=padding.PSS.MAX_LENGTH
            ),
            Prehashed(hashes.SHA256()),
        )
        return True
    except InvalidSignature:
        return False

if is_signature_valid(alice_public_key, received_signature, hash_to_verify):
    print("The signature is valid.")
else:
    print("The signature is not valid.")

Pagkatapos ma-verify ang integridad at pagiging tunay ng natanggap na ciphertext, maaari na si Bob na i-decrypt ito gamit ang kanyang private key dahil nilikha ni Alice ang ciphertext gamit ang public key ni Bob.

# Bob decrypts the message using his private key
decrypted_message = bob_private_key.decrypt(
    received_ciphertext,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("Decrypted message:", decrypted_message.decode())

Sa sitwasyon ng digital signature sa itaas, anumang partido — hindi lamang si Bob — ay makakapag-verify na si Alice ang nagpadala ng ciphertext dahil maaaring ma-access ng lahat ang public key ni Alice, ang ciphertext, at ang digital signature. Bukod pa rito, pagkatapos ipadala ang ciphertext at ang signature, hindi na maaaring itanggi ni Alice na ginawa niya ito dahil ang signature ay maaaring ma-decrypt sa isang makahulugang hash gamit ang kanyang public key lamang. Itinatayo nito ang non-repudiation.

Sa pamamagitan ng pagpapagana ng ligtas na pamamahagi ng key at pagsuporta sa non-repudiation, ang public key cryptography ay nagtatayo ng matibay na pundasyon para sa ligtas na digital na komunikasyon.

Pagsira ng RSA

Ang pagiging kapaki-pakinabang at seguridad ng RSA algorithm na nakabalangkas sa itaas ay nakasalalay sa dalawang matematikal na pagpapalagay:

Ang paghanap ng modular multiplicative inverse $d$ kung ang tanging access lamang ay sa $(e, n)$ ay hindi magagawa sa makatwirang oras ng kompyutasyon.
Sa konteksto ng RSA, ang operasyon ng modular exponentiation ay kumikilos tulad ng isang one-way trapdoor function. Kapag ginamit para sa encryption, nagbubunga ito ng ciphertext na hindi mababasa, at nang wala ang access sa private key, ang pag-invert ng operasyon para mabawi ang plain text mula sa ciphertext ay hindi magagawa. Gayunpaman, kapag may access sa private key na gumaganap bilang trapdoor, madaling ma-decrypt ang ciphertext.

Ang pinaka-kilalang pag-atake sa RSA algorithm ay naglalayong sirain ang pagpapalagay 1 sa pamamagitan ng mahusay na pagbawi ng private key number $d$ sa pamamagitan ng factorization ng modulus $n$ . Tulad ng mailalatag sa ibaba, madaling mabawi ang $d$ kung may access ang isa sa prime factors $p$ at $q$ ng $n$ o sa totient $φ$ $(n)$ . Alalahanin na ang $p$ , $q$ , at $φ$ $(n)$ ay pinananatiling lihim sa panahon ng key generation at tinatanggal pagkatapos. Ang isang third party na nakakabawi ng impormasyong ito gamit ang isang klasikal o quantum na kompyuter ay mahalagang natuklasan ang private key, na sinisira ang RSA. Kaya naman, ang prime factorization ang pangunahing computational primitive na kailangan para sirain ang RSA.

Klasikal na computing at RSA

Ang prime factorization ng malalaking integer ay kilala na nagpapakita ng super-polynomial o subexponential na scaling sa mga klasikal na kompyuter. Ang pinaka-kilalang klasikal na algorithm para sa factoring ng mga integer na mas malaki sa $10^{100}$ ay ang general number field sieve (GNFS)

Matematikal na detalye

$L_n[\frac{1}{3}, (\frac{64}{9})^{(\frac{1}{3})}] = e^{[((\frac{64}{9})^{(\frac{1}{3})} + o(1)) (log(n))^{\frac{1}{3}}(log(log(n))^{\frac{2}{3}})]}$

bilang function ng integer $n$ na ifa-factor.

Ang scaling na ito ay super-polynomial sa bilang ng mga bit na kailangan para katawanin ang $n$ .

Samakatuwid, ang prime factorization ay itinuturing na hindi mahusay sa mga klasikal na kompyuter.

Sa kasalukuyan, ang pinakamalalaking integer na na-factor sa klasikal na hardware ay nasa hanay na 829 bits o 250 decimal na digit. Dahil sa exponential na paglago ng kapangyarihan ng klasikal na computing na nasaksihan sa nakaraang ilang dekada, ang 1024-bit RSA ay hindi na itinuturing na secure sa malapit na hinaharap at na-deprecate na. Gayunpaman, sa nakikitang hinaharap, ang pag-factor ng 2048-bit na mga integer na ang magnitude ay nasa hanay ng $10^{617}$ ay kasalukuyang itinuturing na hindi magagawa sa mga klasikal na sistema, na nagpapahiwatig ng patuloy na pagiging viable. Ang pagdating ng mga quantum na kompyuter, gayunpaman, ay nagpapawalang-bisa ng pagtatasa na ito.

Shor's quantum algorithm at RSA

Marahil ang pinaka-kilalang quantum algorithm ngayon ay ang Shor's algorithm para sa paghanap ng mga prime factor ng mga integer. Nang ipakilala ni Peter Shor noong 1994, kinikilala ito bilang unang quantum algorithm na nag-aalok ng super-polynomial na speedup kumpara sa mga klasikal na algorithm sa isang problemang may malaking praktikal na kahalagahan, lalo na ang prime factorization.

Ang Shor's algorithm ay maaaring mag-factor ng mga prime gamit ang $O(n^2)$ kung saan ang $n$ ay ang bilang ng mga bit.

Matematikal na paliwanag ng Shor's algorithm

Sa konteksto ng RSA, ang Shor's algorithm ay gumagana sa pamamagitan ng pagsasamantala sa periodicity ng modular exponential function $f(x) = a^x (mod~n)$ at nagbibigay ng quantum period-finding primitive na nagbibigay-daan sa mahusay na prime factorization ng modulus $n$ .

Ang isang simplified na mataas na antas na balangkas ng pangkalahatang scheme ni Shor para sa pagsira ng RSA ay ang mga sumusunod:

Dahil sa modulus $n$ , na inilathala bilang bahagi ng public key, pumili ng isang numero $a$ na coprime sa $n$ , ibig sabihin, $gcd(a,n) = 1$ . Dahil alam natin na ang $n = p*q$ ay may eksaktong dalawang prime factor $(p, q)$ , halos kahit anong numero na mas mababa sa $n$ na ating napili nang random ay malamang na coprime sa $n$ .
Pagkatapos mapili ang $a$ , hanapin ang exponent $r$ na $a^r \equiv 1 (mod~n)$ . Ipinahihiwatig nito na $a^r - 1 \equiv 0 (mod~n)$ . Ang pagkakaroon ng isang exponent $r$ na natutugunan ang congruence sa itaas ay ginagarantiyahan ng periodicity property ng modular exponentiation.
Kung ang $r$ ay pantay, $a^r - 1 \equiv 0 (mod~n) \implies (a^{r/2} - 1) (a^{r/2} + 1) = \gamma*n$ para sa ilang integer $\gamma$ . Ang kaliwang bahagi ng huli na pagkakatumbas na ito ay dapat naglalaman ng $p$ at $q$ bilang dalawa sa mga prime factor nito dahil ganoon ang kanang bahagi. Kung ang $r$ ay kakaiba, bumalik sa hakbang 1 at subukan ang ibang pagpipilian para sa $a$ .
Gamitin ang extended Euclid algorithm para sa paghanap ng $gcd((a^{r/2} - 1), n)$ o $gcd((a^{r/2} + 1), n)$ . Ang kinakalkula na GCD ay malamang na makilala ang isa sa mga prime factor $p$ o $q$ . Hatiin ang $n$ gamit ang prime factor na ito para mabawi ang isa pa.
Kapag nakilala na ang $p, q$ , gamitin ang mga hakbang mula sa orihinal na RSA algorithm para muling buuin ang totient $\phi(n)$ at buuin ang private key number $d$ bilang modular inverse ng kilalang public key number $e$ .

Noong Agosto 2023, nag-publish si Oded Regev ng isang pagpapabuti sa orihinal ni Shor gamit ang isang multi-dimensional na diskarte na nagresulta sa $O(n^{1.5})$ . Patuloy pa rin ang karagdagang pananaliksik kabilang na ang ginagawa nina Ragavan at Vaikuntanathan sa larangang ito na maaaring magpabuti ng oras, gastos, o bilang ng mga qubit na kailangan. Bagama't hindi natin masasabi kung kailan talagang magiging viable ang pagpapatakbo ng ganitong mga algorithm laban sa tunay na RSA encryption, lalo itong naglalapitan sa atin.

Halimbawa sa Python na nagpapakita ng pagsira ng RSA encryption

Sa mga sumusunod na code cell, naglarawan tayo ng halimbawa ng paghanap ng isang private key habang binibigyan lamang ng public key. Gagamitin nito ang brute-force na klasikal na kompyutasyon, ngunit ipinapakita kung paano maaaring gamitin ang Shor's algorithm — kabilang ang malalaking key.

tala

Sa seksyong ito, ipapakita natin ang mga matematikal na kalkulasyon nang detalyado bilang bahagi ng Python code

Sa halimbawa, mayroon tayong public key $(5, 247)$ , at mabawi natin ang private key.

Hakbang 1: Ang unang hakbang ay pumili ng isang numero na coprime sa 247. Halos kahit anong numero na ating hulaan ay gagawin ang trabaho. Pumili tayo ng 6.

n = 247  # the modulus
e = 5  # public key number
a = 6  # an integer coprime to n
assert gcd(a, n) == 1
print(f"Checked {n} and {a} are coprime")

Hakbang 2: Susunod, kailangan nating hanapin ang period $r$ na $6^r \equiv 1 (mod~247)$ . Sa halimbawang ito, kinakalkula natin ang $r$ nang klasikal gamit ang brute force, ngunit maaari rin tayong gumamit ng Shor's algorithm sa isang quantum na kompyuter gamit ang Qiskit.

r = 0
rem = 100
while rem != 1:
    r += 1
    rem = (a**r) % n

print(f"period r is: {r}")
assert a**r % n == 1

print(f"Checked {a}^{r} mod {n} is 1")

Hakbang 3: Dahil ang period $r = 36$ ay pantay, maaari tayong mag-compute ng $f1 = (a^{r/2}-1), f2=(a^{r/2}+1)$ .

# explicitly use as integer
f1 = int(a ** (r / 2) - 1)
f2 = int(a ** (r / 2) + 1)

print(f"f1 = {f1}")
print(f"f2 = {f2}")

Hakbang 4: Hanapin ang GCD ng alinman sa mga factor na iyon gamit ang $n$ . Hatiin lamang ang $n$ gamit ang prime factor na nahanap na para makuha ang pangalawang prime factor.

q_found = gcd(f1, n)
print(f"One possible prime factor of n ({n}) is: {q_found}")

# explicit int (to avoid floating point)
p_found = int(n / q_found)
print(f"The second prime factor of n ({n}) is: {p_found}")

assert n == p_found * q_found

Hakbang 5: Pagkatapos mabawi ang mga prime factor ng $n = 247$ bilang $p_{found}=13$ at $q_{found}=19$ , kinakalkula natin ang totient $\phi_{found} = (p_{found}-1)*(q_{found}-1)$ .

Ang private key ay ang modular inverse ng public key number $e=5$ .

# Compute the totient
phi_found = (p_found - 1) * (q_found - 1)
print(f"The totient is: {phi_found}")

# Recover the private key number d_found by satisfying (d_found * e) % phi_found = 1
d_found = 1
while True:
    if (d_found * e) % phi_found == 1:
        break
    else:
        d_found += 1
print("Private Key number:", d_found)

Sa scheme sa itaas, ang hakbang 2 ang mahalagang operasyon ng period-finding kung saan ginagamit ng Shor's algorithm ang dalawang pangunahing quantum primitive, lalo na ang quantum Fourier transform at quantum phase estimation. Para sa detalyadong paliwanag ng mga quantum aspeto ng Shor's algorithm, tingnan ang aralin na Phase estimation and factoring sa Fundamentals of Quantum Algorithms. Ang mga hakbang 1 at 3 hanggang 5 ay nagsasangkot ng mga operasyong medyo hindi mahal na madaling maisagawa sa mga klasikal na kompyuter.

Opsyonal, narito ang isang detalyadong visual na walkthrough ng pagpapatupad ng Shor's algorithm.

Sa mga quantum na kompyuter, ang Shor's algorithm ay maaaring magpakita ng polylogarithmic scaling na kasingabuti ng $O((log~n)^2 (log~log~n))$ sa mga tuntunin ng modulus $n$ , o polynomial scaling sa mga tuntunin ng bilang ng mga bit na kailangan para katawanin ang $n$ . Ito ay isang super-polynomial na speedup kumpara sa klasikal na GNFS algorithm.

Ang mga kamakailang tantya ng resources ay nagpapahiwatig na batay sa ilang mga pagpapalagay na ginawa tungkol sa configuration ng hardware, ilang sampung libo hanggang ilang milyong qubit ang kailangan para sirain ang 2048-bit RSA gamit ang Shor's algorithm. Hindi imposible na ang mga quantum na kompyuter na may ilang sampung libong qubit ay magiging available sa susunod na ilang taon, na ginagawang accessible ang pinakamababang dulo ng tantya ng resources.

Diffie-Hellman key exchange at ang Digital Signature Algorithm

Sa nakaraang seksyon, tinalakay natin ang RSA cryptosystem, na ang seguridad ay batay sa computational na kahirapan ng prime factorization. Dito, tatalakayin natin ang dalawang sikat na asymmetric key cryptographic protocol, ang Diffie-Hellman key exchange (DH) at ang Digital Signature Algorithm (DSA), na parehong batay sa ibang matematikal na problema, lalo na ang discrete logarithm problem (DLP).

Ang discrete logarithm problem

Sa sumusunod na equation kailangan nating hanapin ang $a$ dahil sa $e$ , $M$ , $c$ lamang

$a^e$ $mod$ $M = c$

Ito ay pinaniniwalaan na mahirap sa mga klasikal na kompyuter dahil sa paggamit ng modulo arithmetic, at samakatuwid ay isang magandang matematikal na pundasyon para sa isang encryption algorithm.

Ito ay kilala bilang ang discrete logarithm problem (DLP).

Matematikal na detalye ng discrete logarithm problem

Ang DLP ay karaniwang nakabalangkas sa konteksto ng mga cyclic group at isinasaad tulad ng sumusunod.

Isaalang-alang ang isang cyclic group $G$ na nabuo ng isang group element $g \in G$ at dahil sa isang arbitrary na elemento $h \in G$ , hanapin ang isang integer $k$ na $h = g^{k}$ .

Dito ang integer $k \equiv log_{g}h$ ay ang discrete logarithm. Ang cyclic property ng $G$ ay ginagarantiyahan na para sa bawat $h$ , may valid na integer $k$ na umiiral.

Para sa cryptography, ang DLP sa multiplicative group ng mga integer modulo ang isang prime number $p$ na tinutukoy bilang $(\mathbb{Z}_p)^{\times}$ ay nagpapatunay na kapaki-pakinabang. Ang mga elemento ng $(\mathbb{Z}_p)^{\times}$ ay mga congruence class na may label ng mga integer modulo $p$ na coprime sa $p$ .

Halimbawa:

$(\mathbb{Z}_5)^{\times} = \{[1],[2],[3],[4]\}~\mathrm{and}~(\mathbb{Z}_7)^{\times} = \{[1],[2],[3],[4],[5],[6]\}$

Ang operasyon ng multiplication $(\times)$ sa mga group na ito ay simpleng ordinaryong integer multiplication na sinusundan ng reduction modulo $p$ at ang exponentiation ng isang integer $k$ ay paulit-ulit na multiplication ng $k$ na beses at reduction modulo $p$ .

Ilarawan natin ang isang instance ng DLP sa $(\mathbb{Z}_7)^{\times}$ .

Ang multiplicative group na ito ay may dalawang generator na ${[3],[5]}$ na kilala rin bilang primitive roots. Gagamitin natin ang $[5]$ bilang generator; iyon ay, bubuuin ang bawat elemento ng $(\mathbb{Z}_7)^{\times}$ gamit ang magkakasunod na integer powers ng 5.

#Generate elements of (Z_7)^{x} using generator [5].
g = 5
p = 7
print(f"Using generator {g}")
for k in range(3*p):
    print(f"{g}**{k} mod {p} ≡ {(g**k)%7}")

Nakita natin na sa modulo 7 arithmetic, ang pagdadala ng 5 sa magkakasunod na integer powers ay nagbubunga ng bawat elemento ng $(\mathbb{Z}_7)^{\times}$ nang eksakto isang beses bago paulit-ulit ang cycle nang walang katiyakan na may period na $p-1 =6$ .

Kaya ang DLP sa $(\mathbb{Z}_7)^{\times}$ na may generator [5] ay:

$\mathrm{Given}~h \in (\mathbb{Z}_7)^{\times} \mathrm{, find~} k \mathrm{~such~that~} 5^{k} \equiv h~(mod~7)$ .

Mula sa output ng Python cell sa itaas, nakita natin na:

$h = 2 \implies k=4 \mathrm{~or~} 4 = log_5(2) (mod~7)$

$h = 6 \implies k=3 \mathrm{~or~} 3 = log_5(6) (mod~7)$

Sa ordinaryong real number arithmetic, ang exponentiation ay isang monotonic na function at ang paghanap ng logarithm ng anumang numero sa anumang base ay madaling kalkulahin. Sa kaibahan, tulad ng malinaw mula sa simpleng halimbawa ng $(\mathbb{Z}_7)^{\times}$ sa itaas, ang modular exponentiation ay hindi-monotonic, at kahit na ito ay periodic na may period na $p-1$ , ito ay lubhang hindi trivial. Kaya ang pagkalkula ng inverse nito, ang discrete logarithm, ay lumalabas na hindi mahusay para sa malaking $p$ sa mga klasikal na kompyuter.

Ang obserbasyon na ito ang nagsisilbing pundasyon ng parehong Diffie-Hellman (DH) key exchange at ng Digital Signature Algorithm (DSA), na tatalakayin sa susunod na seksyon.

Ang DLP ay maaaring palawakin sa mga cyclic subgroup tulad ng sumusunod:

Isaalang-alang ang $(\mathbb{Z}_p)^{\times}$ na tinukoy sa itaas at isang elemento $g \in (\mathbb{Z}_p)^{\times}$ ng prime order $r$ iyon ay, $g^r \equiv 1 (~mod~p)$ .
Ang hanay ng mga integer power ng $g$ : $\{g^k~(mod~p) | 1 \le k \le r\} = \langle g \rangle$ ay isang cyclic subgroup ng $(\mathbb{Z}_p)^{\times}$ na may group order $r$ .
Ang isang DLP ay maaaring tukuyin sa $\langle g \rangle$ sa pamamagitan ng pagpili ng $h \in \\langle g \rangle$ at pagtatanong para sa $1 \le a \le r$ na $g^a~(mod~p) = h$

Diffie-Hellman key exchange

Noong 1976, iminungkahi nina Whitfield Diffie at Martin Hellman ang isang key exchange protocol para paganahin ang paglikha ng isang shared secret key sa mga hindi secure na communication channel. Ang secret key ay maaaring magamit ng mga partido na nagbabahagi nito para sa symmetric encryption. Ang algorithm ay umaasa sa DLP.

Figure 1. Diffie-Hellman key exchange

Figure 1. Diffie-Hellman key exchange

Matematikal na detalye ng Diffie-Hellman key exchange

Kung si Alice at Bob ang dalawang partido na nagkokomunika, ang protocol ay gumagana tulad ng sumusunod:

Una, sumasang-ayon sina Alice at Bob sa isang malaking prime number $p$ at isang primitive root o generator $a$ .
Pagkatapos, pumipili si Alice ng isang lihim na exponent $k_A$ nang random na may $1 \le k_A \le p-2$ at kinakalkula ang $h_A = a^{k_A}~(mod~p)$ . Ang $k_A, h_A$ ay ang private at public key ni Alice ayon sa pagkakasunod.
Susunod, pumipili si Bob ng isang lihim na exponent $k_B$ nang random na may $1 \le k_B \le p-2$ at kinakalkula ang $h_B = a^{k_B}~(mod~p)$ . Ang $k_B, h_B$ ay ang private at public key ni Bob ayon sa pagkakasunod.
Pagkatapos, nagpadala si Alice kay Bob ng $h_A$ at nagpadala si Bob kay Alice ng $h_B$ sa isang maaasahan ngunit hindi necessarily secure na channel.
Pagkatapos, ginagamit ni Alice ang $h_B$ na natanggap niya para kalkulahin ang shared secret key na $\kappa = h_B^{k_A}~(mod~p)$ .
Sa wakas, samantala ginagamit ni Bob ang $h_A$ na natanggap niya para kalkulahin ang shared secret key na $\kappa = h_A^{k_B}~(mod~p)$ .

Sa protocol na ito,

Garantisadong matatapos sina Alice at Bob na may parehong secret key $\kappa$ dahil ang $h_B^{k_A}~(mod~p) = (a^{k_B})^{k_A}~(mod~p) = a^{k_A k_B}~(mod~p) = (a^{k_A})^{k_B}~(mod~p) = h_A^{k_B}~(mod~p)$ .
Ang isang third party na humarang sa $h_A$ o $h_B$ ay hindi makakagawa ng secret key $\kappa$ dahil wala silang access sa $k_B$ o $k_A$ ayon sa pagkakasunod.
Ang pagkuha ng $k_A$ o $k_B$ gamit ang pampublikong impormasyon na $a$ , $p$ , $h_A$ at $h_B$ ay computationally mahirap dahil ito ay katumbas ng paglutas ng DLP sa $(\mathbb{Z}_p)^{\times}$ .

Ilustrasyon ng Diffie-Hellman protocol sa Python

Tingnan natin ang isang simpleng halimbawa ng DH protocol sa Python gamit ang maliliit na prime number:

tala

Sa seksyong ito, ipapakita natin ang mga matematikal na kalkulasyon nang detalyado bilang bahagi ng Python code

Hakbang 1: Sumasang-ayon sina Alice at Bob sa isang prime $p$ at isang primitive root $a$ . Pumili tayo ng $p=11, a=7$ .

# Step 1: Choose a prime `p` and a primitive root `a`
p = 11
a = 7

print(f"prime: {p}")
print(f"primitive root: {a}")

Mga Hakbang 2, 3: Pumipili si Alice ng lihim na exponent $k_A$ at kinakalkula ang $h_A = a^{k_A}~(mod~p)$ . Katulad nito, pumipili si Bob ng lihim na exponent $k_B$ at kinakalkula ang $h_B = a^{k_B}~(mod~p)$ .

k_A = 4  # Alice's private key
h_A = (a ** (k_A)) % p  # Alice's public key

print(f"Alice's private key is {k_A} and public key is {h_A}")

k_B = 8  # Bob's private key
h_B = (a ** (k_B)) % p  # Bob's public key

print(f"Bob's private key is {k_B} and public key is {h_B}")

Hakbang 4: Ini-broadcast ng dalawang partido ang kanilang mga public key na $h_A$ at $h_B$ .

Mga Hakbang 5, 6: Pinagsasama ng bawat partido ang kanilang private key sa public key ng kabilang partido para likhain ang shared secret key.

secret_key_alice = h_B**k_A % p
secret_key_bob = h_A**k_B % p
assert secret_key_alice == secret_key_bob
print(f"The shared secret key is: {secret_key_bob}")

Maaari na ngayong gamitin nina Alice at Bob ang shared secret key para sa symmetric encryption.

Seguridad ng Diffie-Hellman key exchange

Tulad ng nabanggit sa itaas, ang seguridad ng DH ay nakabatay sa computational na kahirapan ng paglutas ng DLP gamit ang malalaking prime $p$ . Sa karaniwang mga aplikasyon, inirerekomenda ng NIST ang 2048- o 3072-bit na prime integer para sa DH key exchange, na itinuturing na sapat na secure laban sa mga pagtatangkang lutasin ang DLP gamit ang mga klasikal na kompyuter.

Mga pag-atake ng Man-in-the-middle (MITM): Ang katotohanan na ang DH ay isang interactive na scheme kung saan ang shared secret ay nakasalalay sa pagsasama ng private key ng isang partido sa public key ng kabilang partido ay ginagawa itong mahina laban sa tinatawag na Man-in-the-middle (MITM) na pag-atake.

Matematikal na detalye ng seguridad ng DH at mga pag-atake ng MITM

Sa sitwasyong ito, ang isang third party — sabihin nating si Eve — ay humarang sa mga public key na $h_A, h_B$ sa panahon ng pagpapadala at pinapalitan ang kanyang sariling public key na $h_E$ para sa bawat isa sa $h_A$ at $h_B$ bago ipadala ang mga ito sa Bob at Alice ayon sa pagkakasunod.

Pagkatapos, sa halip na gamitin ang $h_B$ para likhain ang kanyang shared secret, gagamitin ni Alice ang $h_E$ habang iniisip niya na ginagamit niya ang public key ni Bob. Katulad nito, sa halip na gamitin ang $h_A$ para likhain ang kanyang shared secret, gagamitin ni Bob ang $h_E$ habang iniisip niya na ginagamit niya ang public key ni Alice.

Dahil ang $h_E$ ay ginamit para likhain ang shared secret ni Alice (ni Bob), ang plain text na naka-encrypt ni Alice (ni Bob) ay maaaring ma-decrypt ni Eve.

Kaya naman, ang DH key exchange ay karaniwang ginagamit kasabay ng isang digital signature algorithm para masiguro na ang bawat partido ay gumagamit ng authenticated na public key para sa paglikha ng kanilang shared secret.

Ang Digital Signature Algorithm (DSA)

Kahit na ang mga generic na cryptosystem tulad ng RSA ay nagbibigay ng digital signature functionality, noong 1994 ay nag-adopt ang NIST ng isang espesyalisadong signature scheme batay sa modular exponentiation at ang discrete logarithm problem bilang federal standard para sa mga digital signature. Ang scheme na ito, na naging kilala bilang Digital Signature Algorithm (DSA), ay nagsasangkot ng apat na magkakaibang phase:

Key generation:

Ang mga DSA key ay nabuo mula sa:
- 2 prime na nakakatugon sa ilang partikular na patakaran
  - $p$ - karaniwang 256 bits (tatawagin nating ang haba na ito ay $N$ )
  - $q$ - karaniwang 3072 bits (tatawagin nating ang haba na ito ay $L$ )
- Isang cryptographic hash function na mag-co-convert mula sa mga string na may haba $L$ sa $N$
- Isang karagdagang parameter $g$ (tingnan ang mga detalye sa ibaba)
Mula dito, pumipili tayo ng random na numero $x$ bilang private key, at makakakalkula tayo ng public key $y$
Matematikal na detalye ng key generation
- Parameter generation: Sa matematika, ang DSA ay nagsasangkot ng isang cyclic subgroup ng $(\mathbb{Z}_p)^{\times}$ na nabuo ng isang elemento $g$ ng prime order q < p. Ang unang hakbang sa DSA ay samakatuwid pumili ng dalawang prime p, q para magtayo ng mga kinakailangang matematikal na istruktura.
  
  Pumili ng isang $N$ -bit prime $q$ .
  
  Pumili ng isang $L$ -bit prime $p$ na $p-1$ ay multiple ng $q$ . Ang pagpili ng $p$ ay nagtatakda ng group $(\mathbb{Z}_p)^{\times}$
  
  Pumili ng isang integer $1 < h < p-1$ nang random at kalkulahin ang $g = h^{(p-1)/q}~mod~p$ . Kung ang $g=1$ na bihirang mangyari, subukan ang ibang h.
  
  I-verify na ang $g^q~mod~p = 1$ . Ang g ay kaya isang generator ng isang cyclic subgroup $\langle g \rangle$ ng $(\mathbb{Z}_p)^{\times}$ ng prime order q.
  
  Ang mga parameter $(q, p, g)$ ay nagtatakda ng isang instance ng algorithm at pampublikong impormasyon. Karaniwang, ang $N \sim 256$ at $L \sim 3072$ sa mga makatotohanang aplikasyon.
  
  Ang protocol ay nangangailangan din ng isang cryptographic hash function $H : \{0,1\}^L \rightarrow \{0, 1\}^N$ na nagma-map ng mga binary $L$ -bit na string sa mga $N$ -bit na string, halimbawa, SHA-256.
- Key-pair generation: Kailangang bumuo ang signer ng isang key pair sa kanilang dulo.
  
  Pumili ng isang random na lihim na integer $x \in \{1,2...q-1\}$ . Ang $x$ ay ang private key.
  
  Bumuo ng $y = g^{x}~mod~p$ . Ang $y$ ay ang public key ng signer.
Key distribution:

Ang sumusunod na impormasyon ay ibinabahagi sa sinumang nais mag-validate ng isang signature
- Ang mga parameter na ginamit $(p,q,g)$ na naglalarawan ng algorithm
- Ang hash function $H$
- Ang public key $y$
Signing:
- Maaari na ngayong pirmahan ng signer ang isang mensahe $m$ . Ang resultang signature ay $(r,s)$
- Ang mensahe at signature ay parehong ipinapadala sa tatanggap
Matematikal na detalye ng pagpirma ng mensahe
Pinirmahan ng signer ang mensahe $m$ tulad ng sumusunod:
- Pumili ng lihim na integer k nang random mula sa $\{1,2...q-1\}$
- Kalkulahin ang $r = (g^k~mod~p)~mod~q$ . Sa bihirang pagkakataon na $r=0$ , subukan ang ibang random k.
- Kalkulahin ang $s = (k^{-1} (H(m) + xr))~mod~q$ . Sa bihirang pagkakataon na $s=0$ , subukan ang ibang random k.
- Ang signature ay ang tuple $(r, s)$ .
- Ipinadadala ng signer ang mensahe $m$ pati na rin ang signature $(r,s)$ sa verifier.
Dahil parehong integer ang $r, s$ , modulo $q$ ang laki ng signature ay nasa order ng $N$ -bits at hindi ang mas mahabang $L$ -bits.
Verification:

Nais ngayon ng tatanggap na i-verify ang pagiging tunay ng nagpadala. Mayroon silang access sa pampublikong impormasyon $(q, p, g, H, y, (r,s), m)$ Maaari silang magsagawa ng isang kalkulasyon na nagpapatunay na ang nagpadala ay may access sa private key $x$

at nagsisikap na matiyak na ang signer ay may access sa private key $x$ .
Matematikal na detalye ng DSA verification scheme
- I-verify na ang $0 \lt r \lt q$ at $0 \lt s \lt q$ , iyon ay, ang $r, s$ ay mga valid na modulo~q integer.
- Kalkulahin ang $w = s^{-1}~mod~q$ .
- Kalkulahin ang $u_1 = H(m)w~mod~q$ .
- Kalkulahin ang $u_2 = rw~mod~q$ .
- Kalkulahin ang $v = (g^{u_1}y^{u_2}~mod~p)~mod~q$ .
- Ang signature ay na-verify kung ang $v = r$ .
Para sa mga lehitimong signature, ang kawastuhan ng DSA algorithm ay madaling ipakita tulad ng sumusunod:
- Sa dulo ng signer: $s = (k^{-1} (H(m) + xr))~mod~q \implies k = ((H(m) + xr)s^{-1})~mod~q$
- Isaalang-alang ang kanang bahagi ng huli na pagkakatumbas, maaaring kalkulahin ng verifier ang $s^{-1}, H(m)$ dahil ang $s, q, m, H$ ay pampublikong impormasyon.
- Kaya, kinakalkula ng verifier ang $w = s^{-1}~mod~q$ at $u_1 = H(m)w~mod~q = H(m)s^{-1}~mod~q$ .
- Kinakalkula rin ng verifier ang $u_2 = rw~mod~q = rs^{-1}~mod~q$ dahil ang $r$ ay pampubliko rin.
- Pansinin na ang $k = (u_1 + xu_2)~mod~q$ .
- Gayunpaman, ang verifier ay walang access sa $x$ dahil ito ang private key ng signer, kaya ang $k$ mismo ay hindi direktang makakalkula. - Sa halip, ang scheme ay umaasa sa katotohanan na kahit hindi makalkula ng verifier ang $k$ , sa isang lehitimong signer, ang verifier ay dapat na makapag-re-compute ng $(g^k~mod~p)~mod~q = r$ sa tulong ng public key ng signer na $y = g^{x}~mod~p$ .
- Kaya, kinakalkula ng verifier ang $v = (g^{u_1}y^{u_2}~mod~p)~mod~q = (g^{u_1}g^{xu_2}~mod~p)mod~q = (g^{u_1+xu_2}~mod~p)mod~q = (g^k~mod~p)mod~q$ .
- Ang huling pagkakatumbas ay sumusunod dahil ang $g$ ay may order $q$ at nagtatag ng $v = r$ para sa mga valid na signature.

Ilustrasyon ng DSA sa Python

Sa halimbawang ito, gagamit tayo ng maliliit na prime number para mailarawan ang proseso ng DSA sa senaryo kung saan nagpapadala si Alice ng nilalagdaang mensahe kay Bob. Gagamit tayo ng maliliit na integer dito. Sa tunay na mundo, gumagamit ng mas malalaking prime number na nasa hanay ng 2048–3072 bits.

tala

Maaari mong subukang patakbuhin muli ang halimbawang ito gamit ang iba't ibang halaga para makita kung paano kumikilos ang algorithm, ngunit tiyaking sisimulan mo mula sa unang cell ng seksyong ito.

Magsisimula tayo sa pag-import ng mga kinakailangang library at pagpili ng ating mga parameter. Ang integer na mga parameter na $p$ , $q$ , $g$ ay pampublikong impormasyon, at dapat matugunan ang mga sumusunod na panuntunan:

$p$ , $q$ ay parehong prime
$(p-1) \mod\ q = 0$
$g \ge 2$
$g \le (p-2)$
$g^{(p-1)/q} \mod\ p \neq 1$

from random import randint

# parameter generation: select the primes q, p and generator g:
# EXPERIMENT with the values, they must meet certain rules
# this example code does not verify p,q are prime

q = 11
p = 23
g = 4

assert (p - 1) % q == 0
assert g >= 2
assert g <= (p - 2)
assert (pow(g, (p - 1) / q) % p) != 1

print(f"Public information is good: q={p}, p={q}, g={g}")

Susunod, bubuo si Alice, ang pumipirma, ng kanyang pribadong key.

Ang pribadong key na $k$ (alice-private-key sa Python code) ay dapat matugunan ang:

$k \ge 2$
$k \le (q-1)$

# Alice chooses an integer randomly from {2..q-1}
# EXPERIMENT with the values

alice_private_key = randint(2, q - 1)
# alice_private_key =

assert alice_private_key >= 2
assert alice_private_key <= (q - 1)

print(f"Alice's private key is {alice_private_key}")

Itinatago ni Alice ang kanyang pribadong key.

Susunod, kinokompute ni Alice ang kanyang pampublikong key gamit ang modular exponentiation. Ang pag-invert ng hakbang na ito para mabawi ang pribadong key ay isang halimbawa ng DLP, kaya mahirap itong kalkulahin sa mga klasikal na computer kung saan gumagamit ng malalaking prime number.

Mula sa paliwanag ng matematika sa itaas, alam natin na maaari itong kalkulahin gamit ang formula:

$y = g^{x} \mod\ p$

alice_public_key = pow(g, alice_private_key, p)
# Alternatively can use (g ** alice_private_key) % p

print(f"Alice's public key is {alice_public_key}")

Tulad ng dati, ginagawa ni Alice ang kanyang pampublikong key na available sa pamamagitan ng isang channel na hindi kailangang maging lihim.

Maaari na ngayong pumirma si Alice ng mensahe.

Para sa digital signature scheme, kailangan nating bumuo ng hash na $H(m)$ ng mensaheng $m$ na pipirmahan.

Ipagpalagay nating nagkasundo sina Alice at Bob na gumamit ng partikular na hashing algorithm na may hash length na $N$ na katumbas ng bilang ng bits sa $q$ . Sa simpleng halimbawang ito, hahangganin natin ang mga output ng ating mock hash function sa $q$ . Ang hash function dito ay trivial — simpleng bumubuo ng random na integer.

hash_dict = {}

def mock_hash_func(input_message):
    print(input_message)
    if input_message not in hash_dict:
        hash_dict[input_message] = randint(1, q)
    return hash_dict[input_message]

alice_message = "Inspection tomorrow!"
alice_hash = mock_hash_func(alice_message)  # In reality, you'd use a hash function
print(f"Alice's message hash is: {alice_hash}")

Susunod, kailangang bumuo si Alice ng random na per-message secret number na $k$ pati na rin ang multiplicative inverse nito modulo $q$ para makapag-compute ng lagda.

Maaaring gumamit ng simpleng brute-force algorithm para i-compute ang modular inverse. Gayunpaman, mas mainam na gamitin ang isa sa built-in na Python function na pow tulad ng ipinapakita sa ibaba.

# brute-force implementation to find modular inverse
def modular_inverse(k, q):
    for i in range(0, q):
        if (k * i) % q == 1:
            return i
    print(f"error! no inverse found! for {k},{q}")
    return 0

# Let's compare this algorithm with the standard python 'pow' function

n1 = modular_inverse(3, 7)
n2 = modular_inverse(4, 11)
n3 = modular_inverse(7, 5)
m1 = pow(3, -1, 7)
m2 = pow(4, -1, 11)
m3 = pow(7, -1, 5)

assert n1 == m1
assert n2 == m2
# assert(n3==m3)

print(f"modular_inverse(3,7) = {m1}")
print(f"modular_inverse(4,11) = {m2}")
print(f"modular_inverse(7,5) = {m3}")

# Some numbers don't have modular inverses - our function throws an error
n4 = modular_inverse(2, 6)

# The python library will throw an exception, which must be caught
if math.gcd(2, 6) == 1:
    m4 = pow(2, -1, 6)
else:
    print("Exception from pow() - no modular inverse found!")

Maaari na ngayong i-compute ni Alice ang lagda.

$r = (g^{k} \mod p) \mod\ q$
$s = (k^{-1} (H(m) + xr)) \mod q$

Pansinin na may ilang partikular na kondisyon na magpapailangan sa atin na pumili ng ibang halaga para sa $k$ sa kaso kung saan ang $r$ o $s$ ay nag-compute sa $0$ . Sa kasong ito, bubuo tayo ng bagong halaga at uulitin.

# Start an infinite loop; we will 'break' out of it once a valid signature is found.
while True:
    k = randint(1, q - 1)  # Should be different for every message
    print("Using random k =", k)

    r = pow(g, k, p) % q
    # If r is 0, the value is invalid. Try again with a new k.
    if r == 0:
        print(f"{k} is not a good random value to use to calculate r. Trying another k")
        continue

    s = (pow(k, -1, q) * (alice_hash + alice_private_key * r)) % q
    # If s is 0, the value is also invalid. Try again with a new k.
    if s == 0:
        print(f"{k} is not a good random value to use to calculate s. Trying another k")
        continue

    # If we've reached this point, both r and s are valid. Break the loop.
    signature = (r, s)
    print(f"Alice's signature is : {(r,s)}")
    break

# After the loop, the valid r and s values can be used here.
# print(f"Generated Signature -> r: {r}, s: {s}")

Ini-broadcast ni Alice ang mensahe at ang kanyang lagda sa tatanggap o verifier, si Bob.

Nakuha na dati ni Bob ang pampublikong key ni Alice at maaari na ngayong i-verify ang lagda para ma-authenticate ang kanyang mensahe.

Para magawa ito, nagsasagawa siya ng ilang pagsusuri, pagkatapos ay muli niyang bubuuin ang hash ng broadcast na mensahe ni Alice at kinokompute ang mga auxiliary quantity na $w, u_1, u_2$ at $v$ .

$0 < r < q$
$0 < s < q$
$w = s^{-1} \mod\ q$
$u_{1} = H(m) . w \mod\ q$
$u_{2} = r . w \mod\ q$
$v = (g^{u1}y^{u2} \mod\ p) \mod\ q$

Sa wakas, sinusuri ni Bob kung katumbas ng $r$ ang $v$ . Kung magkapantay sila, napatunayan na ang lagda.

# Bob re-generates message hash using Alice's broadcast message
bob_hash = mock_hash_func(alice_message)

# Bob computes auxiliary quantities w (using modular inverse), u1, u2 and v
w = (pow(s, -1, q)) % q
u1 = (bob_hash * w) % q
u2 = (r * w) % q
v = ((g**u1 * alice_public_key**u2) % p) % q

if v == r:
    print("Signature is valid!")
else:
    print("Signature is invalid!")

Seguridad ng DSA

Sa klasikal na computing, ang seguridad ng DSA ay maaaring maimpluwensyahan ng ilang salik:

Laki ng key: Tulad ng palagi, ang laki ng key ay nagbibigay ng pangunahing proteksyon laban sa brute force attacks. Ang mga modernong aplikasyon na gumagamit ng DSA ay gumagamit ng key size na hindi bababa sa 2048 bits.
Kalidad ng $k$ : Sa DSA, ang bawat lagda ay nangangailangan ng natatangi, random, at lihim na halaga ng $k$ (tingnan sa itaas). Ang pagiging natatangi, entropy, at pagiging lihim ng $k$ ay kritikal, at ang kahinaan sa alinman sa mga aspetong ito ay maaaring makompromiso ang pribadong key na $x$ . Ang mga random number generator na ginagamit para bumuo ng $k$ ay kailangang maging ligtas din ang mga ito.
Lakas ng hash function: Dahil gumagamit ang DSA ng hash function bilang bahagi ng proseso ng pagbuo at pag-verify ng lagda, ang isang mahinang hash function ay maaaring makompromiso ang seguridad ng digital signature. Halimbawa, ang paggamit ng SHA-1 kasama ng DSA ay deprecated na at inirerekomenda ang SHA-2 o mas mataas.

Bukod sa mga ito, ang matibay na implementasyon ng DSA ay dapat ding mag-ingat laban sa iba pang uri ng pag-atake na nagta-target sa asymmetric key cryptography tulad ng dati nang binanggit.

Authenticated key exchange gamit ang Diffie-Hellman at DSA

Ang mga modernong network security protocol, tulad ng Transport Layer Security (TLS) at marami pang iba, ay kinabibilangan ng pagsasama ng mga functionality ng key exchange at authentication. Sa konteksto ng Diffie-Hellman, kailangan ang authentication para maprotektahan laban sa mga MITM attack. Sa mga sumusunod na code cell, inilarawan natin ang isang halimbawa kung saan nagsasagawa sina Alice at Bob ng authenticated key exchange sa pamamagitan ng pagsasama ng mga protocol na Diffie-Hellman at DSA. Para dito, gagamitin natin ang cryptography na Python library.

Figure 2. Authenticated key exchange with Diffie-Hellman and DSA

Figure 2. Authenticated key exchange gamit ang Diffie-Hellman at DSA

Una, nagkakasundo sina Alice at Bob sa isang hanay ng mga DH parameter at bumubuo ng isang hanay ng DH public-private key pair.

# import necessary library modules
from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import dh, dsa

# Generate DH parameters
parameters = dh.generate_parameters(generator=2, key_size=2048)

# Generate Alice's DH private key and public key
alice_dh_private_key = parameters.generate_private_key()
alice_dh_public_key = alice_dh_private_key.public_key()

# Generate Bob's DH private key and public key
bob_dh_private_key = parameters.generate_private_key()
bob_dh_public_key = bob_dh_private_key.public_key()

print("Public and private keys generated for Bob and Alice")

Ini-broadcast ang mga DH public key. Susunod, parehong bumubuo sina Alice at Bob ng hiwalay na key pair para gamitin sa DSA. Ang mga key na ito ay gagamitin naman para lagdaan ang mga DH public key na ipagpapalitan.

# Generate DSA keys for Alice and Bob
alice_dsa_private_key = dsa.generate_private_key(key_size=2048)
alice_dsa_public_key = alice_dsa_private_key.public_key()
bob_dsa_private_key = dsa.generate_private_key(key_size=2048)
bob_dsa_public_key = bob_dsa_private_key.public_key()

print("Additional key pair generated for signing")

Nilalagdaan ni Alice ang kanyang DH public key gamit ang kanyang DSA private key.

# Alice signs
alice_public_bytes = alice_dh_public_key.public_bytes(
    encoding=serialization.Encoding.PEM,
    format=serialization.PublicFormat.SubjectPublicKeyInfo,
)
alice_signature = alice_dsa_private_key.sign(alice_public_bytes, hashes.SHA256())

print("Alice signed public key")

Gayundin, nilalagdaan ni Bob ang kanyang DH public key gamit ang kanyang DSA private key.

bob_public_bytes = bob_dh_public_key.public_bytes(
    encoding=serialization.Encoding.PEM,
    format=serialization.PublicFormat.SubjectPublicKeyInfo,
)
bob_signature = bob_dsa_private_key.sign(bob_public_bytes, hashes.SHA256())

print("Bob signed public key")

Ang mga DH public key at kaukulang mga lagda ay ini-broadcast na ngayon ng parehong Alice at Bob. Pagkatanggap ng pampublikong key at lagda ng kanilang katapat, bine-verify ng bawat partido na valid ang lagda. Sa ganitong paraan, mapipigilan ang MITM attack, dahil alam ni Alice, halimbawa, na ang DH public key ni Bob ay talagang nilagdaan ni Bob at kabaliktaran.

# Alice and Bob verify each other's DH public keys using DSA public keys
# An InvalidSignature exception will occur if they are not valid
alice_dsa_public_key.verify(alice_signature, alice_public_bytes, hashes.SHA256())
bob_dsa_public_key.verify(bob_signature, bob_public_bytes, hashes.SHA256())

print("Signatures are valid")

Pagkatapos ng pag-verify ng lagda, bumubuo sina Alice at Bob ng shared secret, na nagkukumpleto sa key exchange.

# Perform key exchange
alice_shared_key = alice_dh_private_key.exchange(bob_dh_public_key)
bob_shared_key = bob_dh_private_key.exchange(alice_dh_public_key)

print("Shared secrets generated")

Opsyonal, para sa karagdagang seguridad, maaaring gumamit sina Alice at Bob ng espesyalisadong key derivation function tulad ng HKDF para bumuo ng mas ligtas na symmetric key mula sa kanilang shared secret gamit ang mga key stretching na teknik.

# Derive a shared symmetric key using key-stretching
def derive_key(shared_key):
    return HKDF(
        algorithm=hashes.SHA256(),
        length=32,
        salt=None,
        info=None,
    ).derive(shared_key)

alice_symmetric_key = derive_key(alice_shared_key)
bob_symmetric_key = derive_key(bob_shared_key)

assert alice_symmetric_key == bob_symmetric_key
print("Keys checked to be the same")

Pagsira sa Diffie-Hellman at DSA

Parehong ang Diffie-Hellman (DH) at DSA na mga protocol ay kinabibilangan ng pagbuo ng mga pampublikong susi na may anyo na $y = g^{x}~mod~p$ , kung saan ang pribadong susi $x$ ay ang discrete logarithm.

Ang isang umaatake na kayang solusyunan ang isang instance ng DLP ay maaaring ilantad ang pribadong susi ng isa sa dalawang partido at, sa pamamagitan ng pagsasama nito sa pampublikong susi ng pangalawang partido, makakuha ng access sa shared secret. Sa kaso ng DSA, ang isang umaatake na kayang solusyunan ang DLP ay maaaring makuha ang pribadong susi ng nagpirma, na nagpapawalang-bisa sa pangunahing saligan ng isang digital na lagda.

Sa mga klasikal na sistema ng computing, ang DLP ay pinaniniwalaang walang solusyon sa polynomial na oras. Ngunit tulad ng ipinakita ni Peter Shor sa kanyang orihinal na papel noong 1994, ang algorithm ni Shor ay naglulusot din sa DLP sa polynomial na oras sa mga quantum computer.

Ang algorithm ni Shor at ang discrete logarithm problem

Kaya ng algorithm ni Shor na solusyunan ang discrete logarithm problem sa polynomial na oras. Pangunahing nakukuha nito ang kahusayan sa pamamagitan ng paggamit ng mga quantum algorithm na kayang hanapin ang period ng isang function na nakadepende sa input ng problema — na pinagsama pagkatapos sa mas karaniwang mga operasyon.

Mga mathematical na detalye ng algorithm ni Shor

Nagbibigay ang algorithm ni Shor ng mahusay na solusyon sa DLP sa pamamagitan ng pag-map nito sa mas pangkalahatang problema sa group theory na kilala bilang hidden subgroup problem (HSP).

Sa HSP, ibinibigay ang isang algebraic group $G$ at isang function $f: G \rightarrow X$ mula sa $G$ patungo sa ilang set $X$ na kung saan ang $f$ ay constant sa bawat coset ng ilang subgroup $H$ ng $G$ (at natatangi sa iba't ibang cosets). Pagkatapos, ang gawain ay tukuyin ang $H$ . Alam na ang mga quantum computer ay kayang solusyunan ang HSP sa mga finite Abelian group sa oras na polynomial sa $log~|G|$ kung saan ang $|G|$ ay ang order ng grupo.

Sa kaso ng integer DLP na tinalakay sa araling ito, ang pag-map sa HSP ay ganito:

Hayaan na ang $p$ ay isang prime at isaalang-alang ang DLP na ibinigay ng $y = g^r~mod~p$ kung saan ang $g$ ay isang generator ng $(\mathbb{Z}_p)^{\times}$ . Dahil ang $g^{p-1} \equiv 1~mod~p$ , ang $g$ ay may order $p-1$ .
Pumili ng $G = \mathbb{Z}_{p-1} \times \mathbb{Z}_{p-1}$ kung saan ang $\mathbb{Z}_{p-1}$ ay ang grupo ng mga integer modulo $(p-1)$ .
Pumili ng $f : G \rightarrow (\mathbb{Z}_p)^{\times}$ na ibinigay bilang $f(a, b) = g^a y^{-b}~mod~p \equiv g^{a-rb}~mod~p$ .
Ang kernel ng $f$ ay ang subgroup na $H_0 = \langle (r, 1) \rangle = \{(a,b) \in G | f(a,b) \equiv 1~mod~p\} = \{ (a, b) \in G | a - rb \equiv 0~mod~(p-1)\}$ .
Ang $f$ ay constant sa mga coset na $(\delta, 0) + H_0$ at "itinatago" ang subgroup $H_0$ na nagtatayo ng isang HSP.

Batay sa nabanggit, ang quantum algorithm ni Shor para sa integer DLP ay gumagamit ng quantum oracle para suriin ang function $f$ sa isang estado na kumakatawan sa uniform superposition sa ibabaw ng $G$ , at pagkatapos ay gumagamit ng quantum Fourier transform at mga sukat na may phase estimation upang makagawa ng mga quantum state na nagbibigay-daan sa pagkilala ng generator na $(r, 1)$ ng $H_0$ . Mula rito, ang $r$ , ang discrete logarithm na kinauukulan, ay maaaring makuha.

Ang orihinal na papel ni Shor ay may detalyadong paglalarawan ng algorithm.

Elliptic curve cryptography

Ang Elliptic curve cryptography (ECC), batay sa matematika ng mga elliptic curve, ay nag-aalok ng makapangyarihang paraan para sa asymmetric key cryptography. Kilala ang ECC na nagbibigay ng katulad na antas ng seguridad tulad ng mga pamamaraan gaya ng RSA ngunit may mas maikling mga susi, na ginagawa itong mas mahusay at partikular na angkop sa mga sistema na may limitadong mapagkukunan, tulad ng mga embedded system at mobile device, kung saan ang pagtitipid sa imbakan at pagkukuwenta mula sa mas maliliit na sukat ng susi ay lubhang kanais-nais.

Mga pangunahing prinsipyo ng elliptic curve cryptography

Ang isang elliptic curve ay karaniwang may anyo na $y^2 = x^3 + ax + b$ na may ilang kawili-wiling katangian.

Ito ay pahalang na simetriko. Kaya para sa anumang punto $(x,y)$ sa kurba, ang kanyang repleksyon na $(x,-y)$ ay nasa kurba rin.
Anumang hindi vertical na tuwid na linya ay magtatawid lamang sa kurba sa maximum na tatlong punto.

Figure 1. Operations of addition and point doubling on an elliptic curve. Facet 1 defines P + Q = -R. Facet 2 illustrates point doubling 2Q = -P. Facet 3 defines the additive inverse of a point as its reflection about the x-axis i.e, P = -Q

Figure 1. Operations of addition and point doubling on an elliptic curve. Facet 1 defines P + Q = -R. Facet 2 illustrates point doubling 2Q = -P. Facet 3 defines the additive inverse of a point as its reflection about the x-axis i.e, P = -Q

Ang elliptic curve cryptography ay gumagamit ng paglapat ng isang serye ng mga aritmetikong operasyon sa mga punto sa kurba. Bawat isa ay epektibong nagdadala sa isang bagong punto sa kurba. Ito ay isang simpleng prosesong sundan sa isang direksyon, at sa mas maikling sukat ng susi ay mas mahusay kaysa sa iba pang mga algorithm tulad ng RSA, ngunit ang pagsubok na baligtarin ito ay napakahirap, kaya naman ginagamit ito sa cryptography.

Mga mathematical na prinsipyo ng elliptic curve cryptography

Ang isang elliptic curve sa isang algebraic field $K$ ay tinukoy ng isang mathematical equation, karaniwang may anyo na $y^2 = x^3 + ax + b$ na may mga coefficient na $a, b \in K$ at naglalarawan ng mga punto $(x, y) \in K \otimes K$ na may karagdagang kinakailangan na ang kurba ay walang mga kink o self-intersection.

Ang mga katangian ng mga elliptic curve ay nagpapahintulot na ang mga operasyon ng "addition" at "scalar multiplication" ay matukoy na kinabibilangan ng mga punto sa kurba.

Addition: Kung ang $P$ at $Q$ ay dalawang punto sa isang elliptic curve, ang $P + Q$ ay naglalarawan ng isang natatanging ikatlong punto na natutukoy tulad ng sumusunod: Iguhit ang linya na tumutugma sa $P$ at $Q$ at hanapin ang ikatlong punto, $R$ , kung saan muling tumutugma ang linya sa kurba. Tinutukoy natin ang $P + Q = −R$ , ang punto na kabaligtaran ng $R$ na nairerepresenta sa pamamagitan ng $x$ -axis (tingnan ang pigura sa ibaba). Kapag ang linya sa pamamagitan ng $P, Q$ ay hindi tumutugma sa kurba sa anumang finite na $(x, y)$ , sinasabi nating ito ay tumutugma sa kurba sa punto sa infinity na $\mathbf{O}$ .

Ang elliptic curve addition ay nakakatugon sa algebraic group na mga katangian na may punto sa infinity bilang additive identity.

Doubling at scalar multiplication: Ang operasyon ng point doubling na tumutugma sa scalar multiplication ng $2$ ay nakuha sa pamamagitan ng pagtatakda ng $P = Q$ sa operasyon ng addition at grapikal na kinabibilangan ng tangent line sa $P$ . Ang pangkalahatang scalar multiplication ng isang integer $n$ na tinukoy bilang $nP = P + P + ...~n$ beses ay nakuha sa pamamagitan ng paulit-ulit na doubling at addition.

Elliptic curve discrete logarithm problem

Ang elliptic curve discrete logarithm problem (ECDLP) ay may maraming pagkakatulad sa discrete logarithm problem na tinalakay dati, batay sa mga hamon ng paghahanap ng mga factor.

Ang operasyon ng scalar multiplication sa mga elliptic curve ay nagpapahintulot sa kahulugan ng elliptic curve discrete logarithm problem:

Ibinibigay ang mga punto $P, Q$ sa isang elliptic curve na kung saan ang $Q = nP$ , tukuyin ang $n$ .

Ang problemang ito ay kilala na hindi malulutas sa mga klasikal na computer para sa malaking $n$ at nagbibigay ng batayan para sa cryptographic security.

Mathematical na paglalarawan ng ECDLP

Ang elliptic curve cryptography ay pangunahing batay sa ECDLP na ginawa sa ilang algebraic finite field. Noong 1999, nagrerekomenda ang NIST ng sampung finite field para gamitin sa ECC. Ito ay:

Limang prime field na $\mathbb {F} _{p}$ para sa mga prime $p$ na may sukat na $\{192, 224, 256, 384, 521\}$ bits.
Limang binary field na $\mathbb {F} _{2^{n}}$ para sa $n \in \{163, 233, 283, 409, 571\}$ .

Sa itaas na setup, ang isang ECC-based asymmetric key cryptosystem sa kaso ng prime field ay maaaring tukuyin tulad ng sumusunod:

Pumili ng $p$ mula sa listahan ng mga halagang inirerekomenda ng NIST upang tukuyin ang $\mathbb {F} _{p}$ .
Pumili ng mga parameter na $a, b$ ng elliptic curve.
Pumili ng base point na $G$ na "gumagawa" ng cyclic subgroup sa kurba na may order na $n$ ; iyon ay, ang pinakamaliit na integer na kung saan ang $nG = \mathbf{O}$ .
Kalkulahin ang cofactor na $h = |E(\mathbb {F} _{p})|/n$ kung saan ang $|E(\mathbb {F} _{p})|$ ay ang bilang ng mga punto sa kurba. Ang $h$ ay karaniwang isang maliit na integer.
Ang domain parameters na $(p, a, b, G, n, h)$ ay nagpapahintulot sa pagtukoy ng mga asymmetric key sa ganitong paraan:
- Ang pribadong susi ay isang random na piniling integer $d$ na may kasinlaking bits tulad ng prime $p$ . Dapat itong panatilihing lihim.
- Ang pampublikong susi ay ang resulta ng "pagpaparami" ng base point $G$ ng pribadong susi $d$ . Ito ay karaniwang tinutukoy bilang $Q = dG$ .

Ang pagbawi ng $d$ ay katumbas ng paglutas ng ECDLP, na ipinapalagay na hindi malulutas para sa malaking $d$ . Ang ECDLP ay nagsisilbing batayan para sa key exchange at digital signature scheme sa direktang pagkakatulad sa mga Diffie-Hellman at DSA scheme na tinukoy sa ibabaw ng $(\mathbb{Z}_p)^{\times}$ na tinalakay dati.

Key exchange gamit ang ECC

Isa sa mga pangunahing gamit ng ECC ay sa key exchange protocol na kilala bilang elliptic curve Diffie-Hellman (ECDH). Sa ECDH, bawat partido ay bumubuo ng isang private-public key pair at pagkatapos ay nagpapalitan ng mga pampublikong susi. Bawat partido ay gumagamit ng kanilang sariling pribadong susi at ng pampublikong susi ng kabilang partido upang kalkulahin ang isang shared secret, na maaaring gamitin bilang susi para sa symmetric encryption.

Habang medyo madali itong magsagawa ng point addition sa isang elliptic curve at makuha ang isang pampublikong susi mula sa isang pribadong susi, ito ay computationally infeasible na baligtarin ang proseso at makuha ang isang pribadong susi mula sa isang pampublikong susi. Ang "one-way" na gawi na ito ang nagbibigay ng seguridad sa ECDH key exchange.

Dito, maglalatag tayo ng halimbawa kung paano maaaring magsagawa ng ECDH key exchange gamit ang Python at ang library na cryptography.

from cryptography.hazmat.primitives.asymmetric import ec
from cryptography.hazmat.primitives import hashes

# Each party generates a private key
private_key1 = ec.generate_private_key(ec.SECP384R1())
private_key2 = ec.generate_private_key(ec.SECP384R1())

# They exchange public keys
public_key1 = private_key1.public_key()
public_key2 = private_key2.public_key()

# Each party uses their own private key and the other party's public key
# to derive the shared secret
shared_key1 = private_key1.exchange(ec.ECDH(), public_key2)
shared_key2 = private_key2.exchange(ec.ECDH(), public_key1)

# The shared secrets are the same
assert shared_key1 == shared_key2
print("Keys checked to be the same")

Mga digital na lagda gamit ang ECC

Maaari ring gamitin ang ECC upang makabuo ng mga digital na lagda gamit ang Elliptic Curve Digital Signature Algorithm (ECDSA). Sa ECDSA, lumilikha ang naglalagda ng lagda gamit ang kanilang pribadong susi, at maaaring i-verify ng iba ang lagda gamit ang pampublikong susi ng naglalagda. Tulad ng ECDH, ang seguridad ng ECDSA ay nakasalalay sa ECDLP. Hindi posible na computationally ang magpeke ng lagda nang walang access sa pribadong susi ng naglalagda.

Ang sumusunod ay isang halimbawa ng simpleng sign-and-verify na transaksyon gamit ang ECDSA na may Python at cryptography.

from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import ec

# Generate a private key for use in the signature
private_key = ec.generate_private_key(ec.SECP384R1())

message = b"A message to be signed"

# Sign the message
signature = private_key.sign(message, ec.ECDSA(hashes.SHA256()))

# Anyone can verify the signature with the public key
public_key = private_key.public_key()

def check_ecdsa_signature(public_key, signature, message):
    try:
        public_key.verify(signature, message, ec.ECDSA(hashes.SHA256()))
        return True
    except InvalidSignature:
        return False

if check_ecdsa_signature(public_key, signature, message):
    print("The signature is valid.")
else:
    print("The signature is invalid.")

Sa code sa itaas, kung babaguhin ng isa ang mensahe pagkatapos itong mapirmahan, ang pag-verify ay mabibigo, na nagbibigay ng garantiya ng pagiging tunay at integridad ng mensahe.

Pagsira sa ECDH at ECDSA

Sa katulad na paraan sa integer discrete logarithm problem, ang ECDLP ay lumalabas na mahirap sa mga klasikal na computer ngunit may mahusay na solusyon sa mga quantum computer muli sa pamamagitan ng algorithm ni Shor. Itinuturo namin kayo sa kamakailang literatura para sa talakayan na may kaugnayan sa pagpapalawig ng algorithm ni Shor sa kaso ng ECDLP.

Buod

Sa araling ito, nagsimula tayo sa pagtingin sa mga pangunahing katangian ng asymmetric key cryptography (AKC) at tinalakay ang mga pangunahing pagsasaalang-alang sa seguridad na nagtataglay ng mga asymmetric cryptosystem. Sa partikular, ipinakilala natin ang dalawang pangunahing aplikasyon ng AKC — iyon ay, ang key exchange at mga digital na lagda — parehong mahalagang bahagi ng modernong komunikasyong batay sa internet.

Pagkatapos, tumingin tayo sa RSA cryptosystem, na mula pa noong 1970s, ay napatunayang napakahalaga para sa pagse-secure ng modernong digital na komunikasyon sa pamamagitan ng pagbibigay-daan sa key exchange at mga digital na lagda sa loob ng isang simple at versatile na balangkas. Ang cryptographic security ng RSA kaugnay ng klasikal na computing ay batay sa kahirapan ng factoring ng malalaking integer at nangangailangan ng mga sukat ng susi na nasa hanay ng 2048 bits upang matiyak na ang mga integer na ginagamit sa mga praktikal na aplikasyon ay sapat na laki para labanan ang factorization.

Pagkatapos, tumingin tayo sa Diffie-Hellman (DH) key exchange at ang Digital Signature Algorithm (DSA). Ang seguridad ng mga scheme na ito ay nakabatay sa integer discrete logarithm (DLP) problem, ang pribadong susi ay computationally mahirap na kunin batay sa pampublikong susi, na walang solusyon sa polynomial na oras sa mga klasikal na computer. Ang paggamit ng mga random at natatanging susi ay nagbibigay ng karagdagang seguridad laban sa mga pag-atake. Parehong ang integer finite field at elliptic curve na mga variant ng DH at DSA protocol ay kasalukuyang malawakang ginagamit sa maraming modernong digital na komunikasyon protocol tulad ng TLS, SSH, at iba pa.

Sa wakas, tumingin tayo sa Elliptic curve cryptography. Sa mahusay na sukat ng susi at matibay na mga katangian ng seguridad, ito ay kasalukuyang kumakatawan sa isang mahusay na pagpipilian para sa maraming cryptographic na aplikasyon, mula sa key exchange hanggang sa mga digital na lagda.

Lahat ng mga algorithm na ito ay nakalantad sa pag-atake mula sa mga quantum algorithm, dahil maaaring bumuo ng mga solusyon upang malutas ang mga mathematical na problema na nagsilbing saligan sa kanilang disenyo. Isang halimbawa nito ay ang algorithm ni Shor. Kaya naman, kailangang palitan ang mga ito ng mga quantum-safe asymmetric cryptosystem na mas matibay laban sa pag-atake mula sa quantum — pati na rin ang pagiging ligtas sa mga klasikal na algorithm. Ang mga mathematical na problema na kanilang inaasahan ay maaaring malutas nang mahusay ng mga quantum computer, na nangangailangan ng pagbuo ng mga quantum-safe asymmetric cryptosystem na kayang labanan ang mga quantum na pag-atake habang pinapanatili ang klasikal na seguridad.

Panimula sa asymmetric key cryptography​

Key exchange gamit ang asymmetric key cryptography​

Interactive key exchange​

Non-interactive key exchange​

Digital signatures gamit ang asymmetric key cryptography​

Mga dedicated na digital signature algorithm​

Mga digital signature scheme gamit ang mga generic na cryptosystem​

Mga aplikasyon ng asymmetric key cryptography​

Seguridad ng asymmetric key cryptography​

Mga panganib sa seguridad ng asymmetric key cryptography​

RSA​

Ang RSA algorithm​

Ilustrasyon ng RSA sa Python​

Paglikha ng RSA key​

Palitan ng symmetric key gamit ang RSA​

Halimbawa ng padding-based na key exchange sa Python​

Pagsimula ng Key Encapsulation Mechanism gamit ang RSA sa Python​

Mga digital signature gamit ang RSA​

Pagsira ng RSA​

Klasikal na computing at RSA​

Shor's quantum algorithm at RSA​

Halimbawa sa Python na nagpapakita ng pagsira ng RSA encryption​

Diffie-Hellman key exchange at ang Digital Signature Algorithm​

Ang discrete logarithm problem​

Matematikal na detalye ng discrete logarithm problem​

Diffie-Hellman key exchange​

Ilustrasyon ng Diffie-Hellman protocol sa Python​

Seguridad ng Diffie-Hellman key exchange​

Ang Digital Signature Algorithm (DSA)​

Ilustrasyon ng DSA sa Python​

Seguridad ng DSA​

Authenticated key exchange gamit ang Diffie-Hellman at DSA​

Pagsira sa Diffie-Hellman at DSA​

Ang algorithm ni Shor at ang discrete logarithm problem​

Elliptic curve cryptography​

Mga pangunahing prinsipyo ng elliptic curve cryptography​

Elliptic curve discrete logarithm problem​

Key exchange gamit ang ECC​

Mga digital na lagda gamit ang ECC​

Pagsira sa ECDH at ECDSA​

Buod​

Panimula sa asymmetric key cryptography

Key exchange gamit ang asymmetric key cryptography

Interactive key exchange

Non-interactive key exchange

Digital signatures gamit ang asymmetric key cryptography

Mga dedicated na digital signature algorithm

Mga digital signature scheme gamit ang mga generic na cryptosystem

Mga aplikasyon ng asymmetric key cryptography

Seguridad ng asymmetric key cryptography

Mga panganib sa seguridad ng asymmetric key cryptography

RSA

Ang RSA algorithm

Ilustrasyon ng RSA sa Python

Paglikha ng RSA key

Palitan ng symmetric key gamit ang RSA

Halimbawa ng padding-based na key exchange sa Python

Pagsimula ng Key Encapsulation Mechanism gamit ang RSA sa Python

Mga digital signature gamit ang RSA

Pagsira ng RSA

Klasikal na computing at RSA

Shor's quantum algorithm at RSA

Halimbawa sa Python na nagpapakita ng pagsira ng RSA encryption

Diffie-Hellman key exchange at ang Digital Signature Algorithm

Ang discrete logarithm problem

Matematikal na detalye ng discrete logarithm problem

Diffie-Hellman key exchange

Ilustrasyon ng Diffie-Hellman protocol sa Python

Seguridad ng Diffie-Hellman key exchange

Ang Digital Signature Algorithm (DSA)

Ilustrasyon ng DSA sa Python

Seguridad ng DSA

Authenticated key exchange gamit ang Diffie-Hellman at DSA

Pagsira sa Diffie-Hellman at DSA

Ang algorithm ni Shor at ang discrete logarithm problem

Elliptic curve cryptography

Mga pangunahing prinsipyo ng elliptic curve cryptography

Elliptic curve discrete logarithm problem

Key exchange gamit ang ECC

Mga digital na lagda gamit ang ECC

Pagsira sa ECDH at ECDSA

Buod