အင္စပတ္တာျမေဝ နွင့္ သုဒၶကိန္းမ်ား

အင္စပတ္တာျမေဝ နွင့္ သုဒၶကိန္းမ်ား

အိုင္ေဆး ကိုပိုင္သြန္ ဟို တေန့ ကေျပာတဲ့ RSA
cryptosystem အေျကာင္းေလး ဆက္စမ္းပါဦး

ေကာင္းပါျပီ ကိုျမေဝ ဒီစနစ္ ကခုေခတ္ အင္တာနက္
ေတြ မွာ အဓိက အသံုးျပုတဲ့စနစ္ေပါ့ Rivest , Shamir နဲ့ Adleman တို့ကိုဂုဏ္ျပု မွည့္ေခါ္ထား
တာေပါ့ သူက အလြန္ျကီးတဲ့ကိန္း ေတြကို ဆခြဲ ကိန္း ခြဲရတာ ခက္တဲ့ အခ်က္ေပါ္ မူတည္ျပီး ျပုလုပ္
ထားတဲ့ စနစ္ေပါ့

ဒီမွာ ပထမ အိုင္ပီ သိဖို့ လိုတာက primes number
သုဒၶ ကိန္းေတြ အေျကာင္း ပါပဲ

prime ဆိုတာ 1 နဲ့ သူကိုယ္တိုင္က လြဲ ရင္စားလို့
မျပတ္တဲ့ ကိန္း မဟုတ္လား ကိုပိုသြန္

ဟုတ္တယ္ ကိုျမေဝ ဥပမာေတြက 3, 5, 7, 11,…… စသျဖင့္ေပါ့ ဗ်ာ 3   ကို  1 နဲ့ 3 ကလြဲရင္စားမရဘူး
တျခားဟာ ေတြလည္း ထိုနည္း၎ ေပါ့

prime ေတြဟာ ဘာလို့ အေရးျကီးလည္း ဆိုေတာ့
ဘယ္ကိန္းကို မဆို prime ေတြ ေျမွာက္ျခင္းနဲ့ ျပုလုပ္ ယူနိုင္တယ္ တနည္းအား ျဖင့္ ကိန္းတိုင္း
ကို ဆခြဲကိန္း ျပန္ခြဲရင္ prime ေတြ ပဲျပန္ရတယ္
ကို ျမေဝ ဥပမာ 10= 3 × 5     , 8= 2×2×2
9=3×3  , 24= 2×2×2×3 စသျဖင့္ေပါ့

ဒီေတာ့ သုဒၶကိန္းေတြ ဟာ မူလဘူတ ကိန္းေတြ
atom of numbers လို့ေျပာလို့ရတယ္ ကိုျမေဝ
ဥပမာ ေရ H₂O ဆိုတဲ့ျဒပ္ေပါင္း ကို H နွစ္လံုး O
တလံုး ဆိုတဲ့ atom ၃ လံုးနဲ့ တည္ေဆာက္ထား
သလိုေပါ့ သူတို့ကိုျက ေတာ့ ထပ္ခြဲလို့ မရေတာ့
ဘူးေပါ့ ဗ်ာ ဒါ ေျကာင့္ စင္ျကယ္တယ္ ဆိုျပီး
သုဒၶ လို့ ေခါ္ဟန္တူပါတယ္ prime ကေတာ့ မူလ
အစ အဦးဆိုတဲ့ အဓိပၸါယ္ မ်ိုးေပါ့ ဒီေတာ့ ကိန္းေတြ
က အနႏၱရွိေပမဲ့ သူတို့ကို ခြဲျခမ္းလိုက္ရင္ေတာ့
ပရိုင္း ေတြပဲက်န္ခဲ့မွာေပါ့ ဒါေပမဲ့လည္း ယူကလစ္
က ပရိုင္းေတြဟာ အနႏၱရွိ တယ္လို့ သူရဲ့ယူကလစ္
က်မ္းမွာ သက္ေသျပခဲ့တယ္ဗ်

အင္း စိတ္ဝင္စားဖို့ေကာင္းသဗ်ာ ဆက္ပါဦး

p နွင့္ q က prime ဆို ရင္ pq = N ဆိုုျပီး ဆခြဲ
ကိန္း ခြဲလို့ရတဲ့ composite number N ကို
လြယ္လြယ္ရွာလို့ရတယ္ဗ် ကြန္ျပူတာမွာေပါ့
ဒါေပမဲ့ ကိုျမေဝ ကို N ေပးထားျပီး p နဲ့ q ကို ျပန္ရွာ
ခိုုင္းရင္ အရမ္းခက္တယ္ဗ် အရမ္းျကီးတဲ့ N ဆိုရင္
ဒါကိုအရမ္းေကာင္းတဲ့ စူပါကြန္ျပူတာနဲ့ေတာင္
အျကာျကီးရွာရတယ္ သူတို့ကို polynomial
time မွာ ရွာရလို့ P ျပသနာလို့ ေခါ္တယ္ဗ်

P ျပသနာ ေတြက အရမ္းခက္ ေပမဲ့ အေျဖရွိေသး
တယ္ေပါ့ဗ်ာ ေနာက္ျပသနာမ်ိုးကေတာ့ exponential time မွာ အေျဖရွာရလို့ ဒီျပသနာမ်ိုး
ကေတာ့ သူတို့ကိုေျဖရွင္း ဖို့ျကာခ်ိန္ဟာ စျကာဝဠာ
သက္တမ္းထက္ျကာ လို့ တနည္း လူ မေျပာနဲ့ ကြန္ျပူ
တာေတာင္ ရွင္းမရ တဲ့ျပသနာမ်ိုးေတြေပါ့ဗ်ာ

ခင္ဗ်ား တကယ္ လို့ သခ်ၤာ နဲ့ ပိုက္ဆံရွာခ်င္ရင္
ဒီျပသနာ ကိုရွင္းဗ် အေမရိကန္နိုင္ငံ Clay university မွာ ဒါကိုရွင္းနိုင္ရင္ ေဒါ္လာ တသန္း
ေပးမယ္လို့ ဆိုထားတယ္ဗ် အဲဒါကေတာ့
P vs NP ျပသနာ ပါ ဆိုလိုတာက NP ျပသနာဟာ
P ျပသနာလိုပဲ ေျဖရွင္းရနိုင္လား မရနိုင္ဘူး လား
တူမလား မတူဘူးလား သက္ေသျပဖို့ပါ

ေျသာ္ ဒါ ကခုထိ မသိေသးဘူးေပါ့ ကိုပိုင္သြန္

ဟုတ္တယ္ ဒါေပမဲ့ ပညာရွင္ အမ်ားစု ကေတာ့
မတူဘူးလို့ ယူဆ ျကတယ္ တခ်ို့ ကေျပာတာေတာ့
P နဲ့ NP ဟာ မတူမွျဖစ္မယ္ ေပါ့ ဘာလို့ ဆို သီခ်င္း
တပုဒ္ ေကာင္းမေကာင္း ကို နား ေထာင္တာ နဲ့ လူ
အမ်ားစုက သိတယ္ေလ ဒါေပမဲ့ လူအမ်ားစု ကို
သီခ်င္းေကာင္းေကာင္း ေရးခိုင္ ရင္ေတာ့ မေရးတတ္ျကဘူးေလ ပါရမီ ရွင္ ဆိုတာ one way
function သို့ one way computation တြင္ ရွိ
ေန လို့သာ ရွိနိုင္တာမ်ိုးကိုး ခုေျပာမဲ့ RSA ကလည္း
prime ေတြေပးထားရင္ N ရလြယ္ေပမဲ့ N ေပး
ထားရင္ primes ေတြျပန္ရဖို့ ခက္တဲ့ အေန အထား
one way process ေပါ္ မွီတည္ေနရတာေပါ့ ကိုျမေဝ

အင္း ဒါေတာ့ စဥ္းစားဖို့ေကာင္းတဲ့ျပသနာေပပဲ

အင္း ေနာက္တခု သိရ မွာ က Euler phi function
Φ(N) ေပါ့ ဒီ ဖန္ရွင္က N ကို ေပးထားရင္ သူ့ေအာက္
မွာ relatively prime ျဖစ္တဲ့ကိန္းအေရအတြက္ကို
ရွာေပတယ္ ေပါ့ဗ်ာ

ကိန္း ၂ ခု က relatively prime ျဖစ္တယ္ဆိုတာ
က သူတို့ နွစ္ဦလံုးကို စားလို့ျပတ္တဲ့ အျကီးဆံုး
ဂဏန္း gcd(greatest common devisor) က 1 ျဖစ္တာကိုေျပာတာဗ်

ဥပမာ  4 နဲ့ 5 ဆို သူတို့ နွစ္ဦးလံုးကို ျပတ္တာ 1 ပဲ ရွိ
တယ္ ဒါေျကာင့္ gcd(4,5)=1 ဒီလိုေရးပါတယ္

4 နဲ့ 6 ဆိုရင္ စားလို့ျပတ္တဲ့ အျကီးဆံုးဂဏန္းက 2
ေပါ့ ဒီေတာ့ gcd(4,6) =2 ဒီလိုေရးပါတယ္

gcd 1 ရတဲ့ ကိန္း ၂ လံုး ကို relatively prime လို့ေခါ္တယ္ 4 နွင့္ 5 ဆို relatively prime ေပါ့ဗ်ာ

ဒီေတာ့ ဒါေေတြေျပာျပရတဲ့ အဓိက အေျကာင္အရင္း
က ဟိုတခါေျပာတဲ့ modular သခ်ၤာ မွာ ခုလို

                  ed=1 (mod Φ(N))

ဆိုတဲ equation မွာ အေျဖရွိ ဖို့ ဆိုရင္

gcd(e,Φ(N))=1

ျဖစ္ဖို့လိုပါတယ္ ဆိုလိုတာက   e နဲ့ Φ(N) သာ
relatively prime ျဖစ္ခဲ့ရင္ e နဲ့ d ေျမွာက္ျခင္းဟာ
1  ရမွာ  တနည္း e ဟာ d ရဲ့ inverse ပါ

ဒီေတာ့ ကိုျမေဝ ဒါေလာက္နားလည္ျပီဆိုရင္ RSA
အေျကာင္းေျပာလို့ရပါျပီ

ဟုတ္ျပီကို ပိုင္သြန္ ဆက္ပါဦး

တကယ္လို့ ကိုျမေဝ က အင္တာနက္ေပါ္က ကုန္
ပစၥည္းတခုခု ေရာင္းမဲ့ စီးပြားေရးသမား ဆိုပါစို့
ဝယ္သူေတြကအမ်ားျကီး သူတို့က ဝယ္ခ်င္ရင္
သူတို့ရဲ့ ဘဏ္ အေကာင့္ ကိုေပးရမယ္ ဒါကို
ျကားကျဖတ္ဖမ္းမိရင္ အႏၱရာယ္ရွိတယ္ ဒီေတာ့
ဒါကို ဝွက္ဖို့ encrypt လုပ္ဖို့ လိုတယ္ အေရးျကီးတာ
ကကိုျမေဝ က encryption key ကို လူေတြအမ်ား
ျကီးသိေအာင္ေျကျငာမယ္ ဒါဆို ဝယ္တဲ့သူက အဲ့
key ကို သံုးျပီး ဝွက္မယ္ ျပီးရင္ ကိုျမေဝ ဆီပို့မယ္
ျကားကလူက ျဖတ္ဖမ္းရင္ ဒါကို encryption key
ျကည့္ယံုနဲ့ မေဖာ္နိုင္ဘူး ဘာလို့ဆို ကိုျမေဝ ဆီမွာ
ပဲ decryption key ေဖာ္တဲ့ေသာ့က ရွိတာေပါ့

၁:  ကိုျမေဝက အေတာ္ျကီးတဲ့ prime number နွစ္ခု p နဲ့ q ကို ေရြးလိုက္ပါ

၂: p နဲ့ q ကို ေျမွာက္ျပီး pq=N ကိုရွာပါ

၃: Φ(N) =Φ(pq)= (p-1)(q-1) ကိုရွာပါ ဒီ function
က N ေပးထားရင္ရွာဖို့ခက္ပါတယ္ ဒါေပမဲ့ N က
prime ျဖစ္ရင္ေတာ့ ခု formula နဲ့ရွာလို့လြယ္ပါ
တယ္

၄: ျပီးရင္ 1< e <Φ(N) နဲ့ gcd(e,Φ(N))=1 ျဖစ္တဲ့ e ကို ေရြးပါ

၅: (e, N) ဒီကိန္း ၂ ခု က public key ပါ တနည္း
ကိုျမေဝ ဆီက ဝယ္မဲ့သူ ဘယ္သူမဆို ဒီနွစ္ခု သံုး
ျပီး သူတို့ bank account နံပါတ္ ကို ဝွက္ရမွာပါ
ဝွက္နည္းက ဥပမာ အေကာင့္က m ဆိုရင္

c = m^e (mod N) ပါ

e နဲ့ N ကိုသံုးျပီး m ကို c ေျပာင္းပါ ျပီးရင္ကိုျမေဝဆီ
ပို့ေပါ့ ဒါဆိုျကားကျဖတ္ဖမ္းသူက m ကိုမသိနိုင္
ေတာ့ဘူး c ကိုပဲရမယ္

၆: ကိုျမ ေဝ က
ed=1(mod Φ(N)) ကေန d ကိုရွာပါ
d ဟာ eရဲ့ multiplicative inverse ပါ တနည္း
decryption key ေသာ့ေပါ့ ဒါကို ကိုျမေဝက သိမ္း
ထားရမွာပါ

၇: ဝယ္သူ ဆီ က  c ေရာက္လာတဲ့အခါ

     c^d=( m^e)^d = m^de=m^1=m

m ကို ရပါျပီ ဒီနည္းနဲ့ျကားက လူက မသိနိုင္ပဲ
ဝွက္စာ ပို့နိုင္ပါျပီ ကိုျမေဝ

အာားးးး ေတာ္ေတာ္ေတာ့ ရႈပ္လဲရႈပ္တယ္ စိတ္ဝင္စား ဖို့လဲေကာင္းတယ္ ကို ပိုင္သြန္
ဒါနဲ့ျကားက လူက N နဲ့ e ကေန d ကိုမရွာ နိုင္ဘူးလား ကိုပိုင္သြန္

ရွာဖို့ခက္တယ္ ကိုျမေဝ အဓိက ကေတာ့ အထက္က
ေျပာ ခဲ့သလိုပဲ N ကေန p နဲ့ q ကို ခြဲဖို့က N သာ
အေတာ္ျကီးမယ္ ဆို အရမ္းျကာမွာပါ p နဲ့ q ရမွ
Φ(N)=(p-1)(q-1) ကေန Φ(N) ရမယ္
အဲ့ကေန e နဲ့ d ကိုရွာနိုင္မွာပါ

ဒီေတာ့ RSA ရဲ့ လံုျခံုေရးဟာ N ကို p နဲ့ q အျဖစ္
uniquely ဆခြဲနိုင္တဲ့အေပါ္မူတည္ တယ္
ကိုျမေဝ ဒါက လက္ရွိေတာ့ အဲ့ program(algorithm) ကို ေရးနိုင္တဲ့သူမရွိေသး
ဘူးေပါ့ ကိုျမေဝ ေရးနိုင္ခဲ့ရင္ ဘဏ္ေတြေဖာက္ျပီး
ခ်မ္းသာျပီေပါ့ဗ်ာ ဟားဟားဟား

ဟား ဒါ ဆိုဒီျပသနာ က အေတာ္ျကီးတာပဲ ကိုပိုင္သြန္

ဟုတ္တာေပါ့ ကိုျမေဝ ဒါေပမဲ့ ဒါကိုလုပ္နိုင္ဖို့က လဲ
number theory မွာ တဖက္ကမ္းခတ္မွပါ ကိုျမေဝ

အင္း ဗဟုသုတ ရပါေပတယ္ ဗ်ာ သိပ္နား မလည္
ေပမဲ့ အေရးျကီးပံု number theory ရဲ့ အသံုးဝင္
ပံုကိုေတာ့ မွန္းမိပါတယ္ဗ်ာ

တခုပဲ က်ုပ္တို့နိုင္ငံသိပ္မတိုးတက္ေသးေတာ့
e commerce ေတြဘာေတြ မရွိေသးေတာ့
တေယာက္ေယာက္ က ဒီလံုျခံုေရးကို ေဖာက္
နိုင္ခဲ့ရင္လည္း စိုးရိမ္စရာေတာ့မရွိေသးပါဘူးဗ်ာ
ဒီလိုျကေတာ့လဲ က်ုပ္တို့ ေခါင္းေဆာင္ေတြရဲ့
အေျမွာ္အျမင္ျကီးမႈ ကို ဝမ့္ေဆြ့ ဝမ့္ေဆြ့
ဝမ့္ဝမ့္ေဆြ့ပါ ဗ်ားးး  ………………………………