Bitcoin ba kamo? on Nostr: RSA Ang RSA Problem ay ganito: - Nabibigay ang mga sumusunod: - May isang integer n, ...
RSA
Ang RSA Problem ay ganito:
- Nabibigay ang mga sumusunod:
- May isang integer n, na produkto ng 2 distinct primes p at q
- Isang positive integer e, kung saan ang gcd(e, (p-1)(q-1)) = 1 (base sa Euler phi function ito: gcd(e, ɸ(n)), at
- Integer c
- Humanap ng integer m, kung saan me ≡ c (mod n)
Ang mga kondisyon sa kung ano dapat ang n at e, ay mahalaga para masiguro na ang bawat integer c ∈ {0, 1, 2, …, n-1} ay may katumbas lamang na isang m ∈ {0, 1, 2, …, n-1}, na magpapatotoo sa me ≡ c (mod n). Sa kontexto ng cryptography, importante ito dahil ang ciphertext na may katumbas na numerong c, ay dapat mayroon lamang isang numerong katumbas na m, na syang representasyon ng plaintext/mensahe.
Dalawang algorithm ang pagdadaanan sa paggamit ng RSA: (1) key generation at (2) encryption.
Key generation (paggawa ng susi):Bawat myembro ng komunikasyon ay gagawa ng kanilang RSA public key at private key. Para magawa ito:
1. Kumuha (random generation) ng 2 malaking distinct primes p at q.
2. Kunin ang n = pq at ɸ = (p-1)(q-1)
3. Pumili ng random na integer e, 1 < e < ɸ, kung saan gcd(e,ɸ) = 1.
4. Kalkulahin ang unique integer na d, 1 < d < ɸ, kung saan ed ≡ 1 (mod ɸ). (Bale ang d ay multiplicative inverse ng e modulo ɸ)
5. Ang public key ay (n, e); at ang private key ay d.
RSA Public-key encryption
1. Encryption:
- Kunin ang public key (n, e) ng pagbibigyan ng mensahe.
- Irepresenta ang mensahe sa anyong integer m na napapaloob sa pagitan ng [0, n-1].
- Kalkulahin ang c = m^e mod n.
- Ipadala ang ciphertext c.
2. Decryption: Para makuha ng tagatanggap ang m mula sa c, gagamitin nya ang kanyang private key d sa komputasyong: m = c^d mod n.
Gumagana ito dahil sa Euler at Fermat’s theorem.
- Dahil ang ed ≡ 1 (mod ɸ), merong integer k na kung saan ed = 1 + kɸ.
- Mula sa Fermat’s theorem: m^(p-1) ≡ 1 (mod p)
- I-raise ang magkabilang panig ng congruence sa k(q-1) at i-multiply ng m ang parehas na panig: m^(1+k(p-1)(q-1)) ≡ m (mod p)
- Makikita sa exponent ng m sa kaliwa na ito ay katumbas ng 1 + kɸ = ed. Kaya, med ≡ m (mod p)
- Gayun din ang kalalabasan para sa modulus q, m^(ed) ≡ m (mod q)
- At dahil ang p at q ay distinct primes, mula sa Euler’s theorem, sumusunod na m^(ed) ≡ m (mod n)
- At sa wakas, c^d ≡ (m^e)^d ≡ m (mod n)
Ang galing noh? Para sa impormasyon ng kompyuter, may paraan dapat na irepresenta ang mensahe sa isang ingeter m. Hindi na natin palalawakin dito kung pano yun gagawin.
Ngayon at nakuha mo na ang konsepto, babanggitin lang saglit ang isang paraan ng assymetric cryptography na gamit sa bitcoin. Sa pagkuha ng public key mula sa private key, gumagamit ng Elliptic Curve Digital Signature Algorithm. Digital signature nanaman - may pag-uusapan muna tayong konsepto bago natin ito balikan.
Ang RSA Problem ay ganito:
- Nabibigay ang mga sumusunod:
- May isang integer n, na produkto ng 2 distinct primes p at q
- Isang positive integer e, kung saan ang gcd(e, (p-1)(q-1)) = 1 (base sa Euler phi function ito: gcd(e, ɸ(n)), at
- Integer c
- Humanap ng integer m, kung saan me ≡ c (mod n)
Ang mga kondisyon sa kung ano dapat ang n at e, ay mahalaga para masiguro na ang bawat integer c ∈ {0, 1, 2, …, n-1} ay may katumbas lamang na isang m ∈ {0, 1, 2, …, n-1}, na magpapatotoo sa me ≡ c (mod n). Sa kontexto ng cryptography, importante ito dahil ang ciphertext na may katumbas na numerong c, ay dapat mayroon lamang isang numerong katumbas na m, na syang representasyon ng plaintext/mensahe.
Dalawang algorithm ang pagdadaanan sa paggamit ng RSA: (1) key generation at (2) encryption.
Key generation (paggawa ng susi):Bawat myembro ng komunikasyon ay gagawa ng kanilang RSA public key at private key. Para magawa ito:
1. Kumuha (random generation) ng 2 malaking distinct primes p at q.
2. Kunin ang n = pq at ɸ = (p-1)(q-1)
3. Pumili ng random na integer e, 1 < e < ɸ, kung saan gcd(e,ɸ) = 1.
4. Kalkulahin ang unique integer na d, 1 < d < ɸ, kung saan ed ≡ 1 (mod ɸ). (Bale ang d ay multiplicative inverse ng e modulo ɸ)
5. Ang public key ay (n, e); at ang private key ay d.
RSA Public-key encryption
1. Encryption:
- Kunin ang public key (n, e) ng pagbibigyan ng mensahe.
- Irepresenta ang mensahe sa anyong integer m na napapaloob sa pagitan ng [0, n-1].
- Kalkulahin ang c = m^e mod n.
- Ipadala ang ciphertext c.
2. Decryption: Para makuha ng tagatanggap ang m mula sa c, gagamitin nya ang kanyang private key d sa komputasyong: m = c^d mod n.
Gumagana ito dahil sa Euler at Fermat’s theorem.
- Dahil ang ed ≡ 1 (mod ɸ), merong integer k na kung saan ed = 1 + kɸ.
- Mula sa Fermat’s theorem: m^(p-1) ≡ 1 (mod p)
- I-raise ang magkabilang panig ng congruence sa k(q-1) at i-multiply ng m ang parehas na panig: m^(1+k(p-1)(q-1)) ≡ m (mod p)
- Makikita sa exponent ng m sa kaliwa na ito ay katumbas ng 1 + kɸ = ed. Kaya, med ≡ m (mod p)
- Gayun din ang kalalabasan para sa modulus q, m^(ed) ≡ m (mod q)
- At dahil ang p at q ay distinct primes, mula sa Euler’s theorem, sumusunod na m^(ed) ≡ m (mod n)
- At sa wakas, c^d ≡ (m^e)^d ≡ m (mod n)
Ang galing noh? Para sa impormasyon ng kompyuter, may paraan dapat na irepresenta ang mensahe sa isang ingeter m. Hindi na natin palalawakin dito kung pano yun gagawin.
Ngayon at nakuha mo na ang konsepto, babanggitin lang saglit ang isang paraan ng assymetric cryptography na gamit sa bitcoin. Sa pagkuha ng public key mula sa private key, gumagamit ng Elliptic Curve Digital Signature Algorithm. Digital signature nanaman - may pag-uusapan muna tayong konsepto bago natin ito balikan.