Ngayon naman ay ipapakilala ang isang simple at eleganteng konsepto na makikita sa asymmetric cryptography, na tinatawag ring public-key cryptography. Nabanggit nang bahagya sa ikalawang kabanata ang konsepto nito nung pinag-uusapan ang digital na pitaka.
Ang public-key cryptography ay gumagamit ng 2 susi: pribado (private) at pampubliko (public). Ang public key ay maaaring ipadala sa hindi sikretong daan, tulad ng ciphertext. At ang private key ay nananatili sa isang user lamang.

Gagamitin ng magbibigay (A) ng mensahe ang public key (e) ng pagbibigyan (B) nya, upang mag-encrypt. Ang ciphertext na ipapadala nya ay made-decrypt ng tagatanggap gamit ang private key (d) nito. Ganun din kung kabaliktaran (B—>A) ang mangyayari.
Ang kalamangan ng pamamaraang ito, ay ang isang user ay merong naitatagong susi na kanya lamang. Para maging epektibo, dapat ang relasyon ng public at private key ay: madaling kunin ang public key mula sa private key. Pero, mahirap makuha ang private key mula sa public key. Nasa may-ari ng private key nakasalalay ang pag-iingat nito. Dahil pag ito nawala, sya mismo ay hindi made-decrypt ang ciphertext.
Maihahalintulad ito sa isang baul at lock. Gamit ang baul at nakabukas na lock ni B, ilalagay ni A ang mensahe sa loob, at isasarado, pati ang lock. Kumbaga ang public key ay ang kombinasyon ng bukas na baul at lock. Ang ciphertext ay ang box na nakakandado. At ang susi ni B ang private key. Pagkasara, hindi na mabubuksan ni A ang lock dahil nakay B lamang ang susi.
At magagawa ang konsepto na ito syempre, gamit ang kapangyarihan ng matematika. Marami sa mga public-key cryptography ay base sa konsepto ng integer factorization problem. Ito ang paghahanap ng prime factors ng isang integer. Halimbawa, ang numerong 65 ay may prime factors na 5 x 13. Sa 98: 2 x 72. Walang shortcut sa pagkuha nito. Kailangan mo lang subukan talaga ang mga posibilidad. Habang lumalaki ang numero, mas humihirap, lalo na kung malalaking prime numbers din ang factors ng isang integer.
Isang popular na public-key cipher ay ang RSA. Madalas itong gamit sa mga internet browser at websites sa kombinasyon ng iba pang cryptography. Dahil na rin nagagamit sa digital signatures ang RSA.
Ang RSA ay ipinangalan kina R. Rivest, A. Shamir at L. Adleman. Para matutukan natin ito, maging pamilyar muna sa mga susunod na konsepto ng matematika:
Konting Number Theory
Konti ba yan?
Integer – Alam mo naman na siguro ito. Basta whole number na pwedeng positive o negative, at 0. Ang set ng integers {…, -3, -2, -1, 0, 1, 2, 3, … } ay ℤ.
Division – maghain tayo ng mga notasyon ukol dito.
- Kapag ang b ay nahahati ng sakto ang a, masasabing “b divides a,” na pwedeng isulat na b|a. Isang paraan lang ito ng pagsasabi na ang b ay divisor ng a, o kaya b ay factor ng a.
- Division algorithm for integers: kapag ang a ay hahatiin ng b, may makukuha tayong quotient q, at kapag di sakto, may remainder r. Kung saan ang relasyong ng a, b, q & r ay maipapakita na: a = qb + r ;
- Ang remainder na r ay maaring irepresenta na a mod b
- Ang quotient q naman ay a div b
- Halimbawa: a = 83, b = 19; ang q = 4 = 83 div 19, at r = 7 = 83 mod 19
- Greatest common divisor (gcd): ito ang pinakamalaking divisor na pareho sa dalawang integer. Halimbawa, dalawang integer, 16 at 24, may mga factors o divisors sila na parehas: {±1, ±2, ±4, ±8}; makikita na ang gcd(16,24) = 8
Relatively prime – Ang dalawang integers a at b ay sinasabing relatively prime (o coprime) kung gcd (a,b) = 1, o wala silang common divisor maliban sa 1. Tandaan na iba ang prime number sa relatively prime. Halimbawa, ang 7 at 8 ay relatively prime dahil ang gcd(7,8) = 1. Pero alam natin na ang 7 ay prime, samantalang ang 8 ay composite na may prime factorization na 23.
Euler phi function o Euler totient function – ni rerepresenta ng ɸ. Para sa isang integer n, ang ɸ(n) ay ang dami ng integers mula 1 pataas, bago mag n, na relatively prime sa n. Halimbawa, ang mga relatively prime sa 9 ay: {1, 2, 4, 5, 7, 8}. Kaya ɸ(9) = 6. May mga katangian (properties) ang Euler phi function:
- Kung ang p ay prime, ang ɸ(p) = p – 1. Halimbawa, ang 7: dahil prime number ito, lahat ng integers bago sya ay relatively prime sa kanya: {1,2,3,4,5,6}. Ito ay mahalagang katangian na nagagamit sa public key cryptography. Makikita mo mamaya (o bukas, bala ka).
- Ang Euler phi function ay multiplicative. Sa dalawang relatively prime m at n, gcd(m,n) = 1, ang ɸ(mn) = ɸ(m) * ɸ(n). Mula sa kaninang nabanggit, gcd(7,8) = 1. Ang ɸ(7) = 6; samantalang ang ɸ(8) = 4: {1,3,5,7}. Mula dito ang ɸ(56) = ɸ(7) * ɸ(8) = 6 * 4 = 24. Kumpirmahin natin. Ang mga relatively prime sa 56 ay: {1, 3, 5, 9, 11, 13, 15, 17, 19, 23, 25, 27, 29, 31, 33, 37, 39, 41, 43, 45, 47, 51, 53, 55} – 24 na integers.
- Kung ang n = p1e1p2e2…pkek ay ang prime factorization ng n, susunod na:

Integers modulo n
- Ang n ay isang integer.
- Kung ang a at b ay integers, masasabing “a is congruent to b modulo n”, na nasusulat na a ≡ b (mod n), kung nadi-divide ng n ang (a – b). Ang integer na n ay tinatawag na modulus ng congruence.
- Halimbawa, 83 ≡ 7 (mod 19), dahil 83 – 7 = 4 * 19; pansinin ang pagkakaiba ng representasyon ng congruence mula sa nabanggit kanina na representasyon ng remainder na 7 = 83 mod 19. Magkabaliktad ng pwesto ang 83 at 7, at napapaloob sa parentheses ang (mod 19) kapag congruence. Pagtutuunan ng pansin maya-maya ang congruence na napapaloob ang remainder sa equation. Pero wag ka malilito kapag hindi iyon tumugma sa ibang congruences na makikita mo. Halimbawa, pag pinagbaliktad natin ang pwesto ng 83 at 7: 7 ≡ 83 (mod 19), tama pa rin ito dahil 7 – 83 = -4 * 19. O kaya naman 249 ≡ 21 (mod 19), iisipin mo ang remainder kapag hinati ng 19 ang 249 ay 2. Pero ang congruence na ito ay tama pa rin dahil 249 – 21 = 12 * 19. Maiintindihan mo pa dahil sa susunod.
- Ang congruence ay may mga katangian na:
- a ≡ b (mod n) if and only if ang a at b ay may parehas na remainder kapag hinati ng n.
- (Reflexivity) a ≡ a (mod n)
- (Symmetry) If a ≡ b (mod n) then b ≡ a (mod n)
- (Transitivity) If a ≡ b (mod n) and b ≡ c (mod n), then a ≡ c (mod n)
- If a ≡ a1 (mod n) and b ≡ b1 (mod n), then a + b ≡ a1 + b1 (mod n) and ab ≡ a1b1 (mod n)
- May tinatawag na equivalence class na syang set ng integers na pare-parehas ng least residue sa isang modulus n. Gamit ang division algorithm: a = qn + r . Sa iba-ibang value ng a, mayroon remainder mula 0 – (n-1). Ang remainder r ay ang least residue ng a modulo n. Kaya ang r ay magagamit na representasyon ng equivalence class.
- Ang integers modulo n, na may simbolong ℤn, ay ang set ng equivalence class ng integers {0, 1, 2, …, n – 1}. Ang mga operasyong addition, subtraction at multiplication ay ginagawa modulo n.
- Halimbawa, ang ℤ19 = {0, 1, 2, …, 18}. Sa ℤ19, 11 + 12 = 4, kasi 23 ≡ 4 (mod 19). Masasabing ang 23 ay nasa equivalence class ng 4. Sa parehas na konsepto, ang 11 * 12 = 18 sa ℤ19, dahil 132 ≡ 18 (mod 19), o ang 132 ay nasa equivalence class ng 18.
- Kapag sa loob ng ℤn ay may integers a at x kung saan ax ≡ 1 (mod n), masasabing ang multiplicative inverse ng a modulo n ay x. Halimbawa, ang 4 at 5 sa ℤ19 ay invertible dahil 45 ≡ 1 (mod 19).
- Mayrong group sa loob ng ℤn na tinatawag na multiplicative group na may notasyong ℤ*n. Ang laman nito ay ang mga elements na relatively prime/coprime sa n.
- Ang order ng ℤn ay |ℤn| o ang bilang ng elements nito. Kaya kung ano ang value ng Euler phi function ɸ(n), iyon ang order ng ℤ*n.
Euler’s theorem:
- Kapag ang integer a sa ℤn ay relatively prime sa n o parte ng ℤ*n, susunod na: aɸ(n) ≡ 1 (mod n)
- Kapag ang n ay produkto ng 2 magkaibang (distinct) primes, at kapag r ≡ s (mod ɸ(n)), susunod na ar ≡ as (mod n) para sa lahat ng integers a.
Fermat’s theorem: Sa isang prime p
- Kung gcd(a,p) = 1, susunod na ap-1 ≡ 1 (mod p)
- Kung r ≡ s (mod p-1), susunod na ar ≡ as (mod p) para sa lahat ng integers a.
- Saka, ap ≡ a (mod p) para sa lahat ng integers a.
Okay, yan na muna. Konti ba yan? Oo konti pa yan. Mula sa mga konseptong nalatag, pag-uusapan na natin ang RSA.
Kitakits sa ika-10.
Salamat sa litrato na dinagdagan at in-edit namin: NEOSiAM 2021: https://www.pexels.com/photo/person-holding-white-chalk-625219/
Pingback: Discrete Logarithm – painit muna bago ang ECDSA – Bitcoin ba kamo?