Digging into RSA Algorithm

အစကဘယ္လိုေရးရမွန္းမသိဘူးကိုျဖစ္ေနတာ ေနာက္ေတာ့လည္း ရွိသမွ်ဟာေတြလိုက္ဖတ္ ေကာင္းတဲ့ရွင္းထားတာေလးေတြမွတ္ထားကေန ခုေတာ့ ေရးလို႕ေတာင္ျပီးသြားပါျပီ။ နည္းနည္းေတာ့ရွုပ္မယ္။ ဒါေပမယ့္လို႕ ေသခ်ာဖတ္ရင္ေတာ့ နားလည္သြားမွာပါ။ နားမလည္ဘူးဆိုလည္း ၀င္ေဆြးေႏြးသြားႏိုင္ပါတယ္။ မွားေနတာတစ္ခုခုကိုေတြ႕တယ္ဆိုရင္လည္း အားမနာနဲ႕ ၀င္ေျပာသြားပါ။ မဟုတ္က ဟုတ္ကၾကီးေရးထားမိရင္သာ ရွက္ရပါလိမ့္မယ္ bebe-pleure
What is RSA ?
RSA ဆိုတာ publick-key ကိုအသံုးျပဳတဲ့ Cryptosystem ျဖစ္ပါတယ္။ Crypto ေတြကိုဘယ္ေနရာမွာသံုးတာလဲဆိုတာေတာ့
ေထြေထြထူးထူးေျပာေနဖို႕လိုေတာ့မယ္မထင္ပါဘူး။ ဆက္ေလ့လာမယ္။ RSA ကို ၁၉၇၇ ခုနစ္မွာ Ron Rivest , Adi Shamir , Leonard Adleman တို႕က စတင္ေဖာ္ျပခဲ့ျခင္းျဖစ္ပါတယ္။ သူတို႕၃ ေယာက္နာမည္ေတြကိုအစြဲျပဳျပီးေတာ ့RSA  (Rivest-Shamir-Adleman) ဆိုျပီးျဖစ္လာခဲ့တယ္။  Publick Key Cryptography လို႕ေခၚတယ္ေနာက္တစ္ခုက Asymmetric cryptography လို႕လည္းေခၚပါတယ္။

ဒီေနရာမွာ Assymetric cryptography အေၾကာင္းေျပာဖို႕လိုလာျပီ။ အရင္ေလ့လာခဲ့တဲ့ cryptography ေတြအကုန္လံုးက symmetric key ေတြျဖစ္ပါတယ္။ ဘာကြားျခားမွဳရွိသလဲဆိုရင္ အရင္ cryptography ေတြမွာ key ကတစ္ခုတည္းပဲ။ Encrypt လုပ္လည္း ဒီ Key ပဲ Decrypt လုပ္မယ္ဆိုလည္းဒီ key ပဲ။ ဒါကိုျမန္မာလိုဆိုရင္ေတာ့ ေခါက္ခ်ိဳးညီတယ္ေပါ့။ ဟုတ္ျပီ Asymmetric မွာေတာ့ ဒီလိုမဟုတ္ေတာ့ဘူး ။ Encrypt လုပ္ဖို႕ကို Key တစ္ခု Decrypt လုပ္ဖို႕ကို Key တစ္ခု။ Encrypt ကို Public-Key နဲ႕လုပ္တယ္ဆို Decrypt လုပ္တဲ့အခါက်ေတာ့ private-key ကိုသံုးမွရမယ္။ ဒီေလာက္နားလည္ထားရင္ရပါျပီ။

[Image: rsa_encryption.jpg]

Encrypt လုပ္တဲ့ public-key ကို လူတိုင္းသိႏိုင္ေပမယ့္ private-key ကိုေတာ့ secret အေနနဲ႕ထားမွျဖစ္ပါလိမ့္မယ္။ ဒါမွသာ လံုျခံဳမွဳရွိေတာ့မွာေပါ့။Protocol ေတြျဖစ္ၾကတဲ့ SSH ,OpenPGP , S/MIME , SSL/TLS စာတာေတြမွာလည္း RSA ကို Encryption အတြက္ရယ္ Digital Signature အတြက္သံုးၾကပါတယ္။ Digital Signature ကိုေအာက္မွာပံုေလးထည့္ေပးထားပါတယ္။

[Image: ss_digitalsignature_2014_v01_desktop.png]

RSA Operation

RSA မွာ Public Key create လုပ္ဖို႕ဆိုရင္ အဓိကလိုအပ္တာကေတာ့ Prime Number ၂ ခုပဲျဖစ္ပါတယ္။ ဒီ prime number ၂ ခုဟာ
လ်ိဳ႕၀ွက္ထားရမွာျဖစ္ပါတယ္။ ဒါဆိုရင္ ပိုျပီးေလ့လာၾကတာေပါ့။ အတတ္ႏိုင္ဆံုးေတာ့ရွင္းျပလိုက္မယ္။ နားမလည္ဘူးဆိုရင္ေတာ့ တစ္မ်ိဳးၾကံၾကတာေပါ့။
ဟုတ္ျပီ Prime Numbers ေတြပါ၀င္တဲ့ ကိန္းေသ ၂ ခုရွိမယ္။ p & q ပဲျဖစ္ပါတယ္။
n = pq ကေတာ့ RSA key ရဲ႕ bit length ပဲျဖစ္ပါတယ္။ ဥပမာ 1024 bits RSA ဘာဘာညာညာေပါ့။
ဟုတ္ျပီေနာ္။ Public Key မွာ modulus n နဲ႕ public exponent e ( ပံုမွန္အားျဖင့္ေတာ့ 65537) တို႕ပါ၀င္မယ္။
Private Key မွာကေတာ့ modulus n နဲ႕ private exponent d တို႕ပါ၀င္ပါတယ္။ d တန္ဖိုးကိုတြက္တဲ့အခါမွာေတာ့ Euler’s Totient ကိုသံုးျပီးတြက္ရမွာျဖစ္ပါတယ္။
ဒါကို ျမန္မာလိုဘယ္လိုေခၚမလဲေတာ့ က်ေနာ္လည္း Maths သမားမဟုတ္ေတာ့မသိေသးဘူး။ အသိထဲမွာလည္း Maths သမားမရွိေတာ့မသိဘူးျဖစ္ေနတယ္။ ေဆာရီးပါ။ ဒါေပမယ့္လို႕စိတ္မပူပါနဲ႕ တြက္တဲ့အခါက်နားလည္ေအာင္ရွင္းျပေပးပါမယ္။
ခုဆို ဖတ္ေနတဲ့သူေတြေတာ္ေတာ္ေလးကိုရွုပ္ကုန္ျပီ။ မွတ္ပဲမွတ္ထားလိုက္ပါ။ Example ေလးေတြလုပ္လိုက္ရင္ နားလည္သြားမွာပါ။

A Simple , worked example

ဟုတ္ျပီ ။ က်ေနာ္ Thin Ba Shane က RSA key တစ္ခုကို generate လုပ္မယ္ဆိုပါေတာ့ဗ်ာ။ Prime Number 2 ခုကို p & q အတြက္ေရြးခ်ယ္လိုက္ျပီ။
p=11 ,  1=13 ။ ဒီေတာ့ modulus n = 143 ျဖစ္သြားျပီ။ Totient Function ကိုသံုးရမယ္။ ဒီေတာ့ကာ
nϕ(n)=(p-1)x(q-1)=(11-1)x(13-1)=120 ။
ေနာက္ျပီးေတာ့က်ေနာ္တို႕ public key အတြက္ e တန္ဖိုးကို 7  လုိ႕ေရြးလိုက္မယ္။  ဘာေၾကာင့္ 7 ကိုေရြးရတာလဲဆိုတာေျပာပါမယ္။ public key အတြက္ e တန္ဖိုးကိုေရြးတဲ့အခါမွာ
Greatest Common Divisor (gcd) ကို ϕ(n) တန္ဖိုးနဲ႕ အနည္းဆံုး 1 ရွိတာကိုေတာ့ေရြးခ်ယ္ဖို႕လိုပါတယ္။
3 , 5 စတဲ့ Prime Number တစ္ခုခုကိုေရြးလိုက္တယ္ဆိုရင္ ϕ(n) တန္ဖိုးျဖစ္တဲ့ 120 နဲ႕ gcd 1 မရွိဘူး။ ဒါေၾကာင့္ေရြးလို႕မရလို႕ 7 ကိုေရြးလိုက္ရတာျဖစ္တယ္။ ဟုတ္ျပီ ။ ဒါဆိုရင္ က်ေနာ္တို႕ e တန္ဖုိုးကို 7 ကိုရျပီဆိုပါေတာ့ ။ private key အတြက္ d
တန္ဖိုးကို တြက္ရမယ္။ ဘယ္လိုတြက္ရမလဲဆိုေတာ့ 7 ရဲ႕ inverse တန္ဖိုးကို ϕ(n) နဲ႕ တြက္ရမယ္။ တြက္ရမယ့္ formula က n-1 = m (mod p) ျဖစ္တယ္။ n = 7 , p=120 ဆိုျပီးတြက္ရမွာေပါ့။ ဒါေပမယ့္ နားလည္ထားရင္ရပါျပီ။
က်ေနာ္ကေတာ့

ေဟာဒီမွာသြားတြက္လိုက္တယ္ဗ်ာ။ Manual နားလည္တယ္ဆိုေပမယ့္ အကုန္လိုက္လုပ္ေနရရင္လည္းေသရခ်ည္ရဲ႕ေပါ့ ။
က်ေနာ္တို႕ရလာတဲ့ d တန္ဖိုး 103 မွန္မမွန္ကို  e.d = 1 mod  ϕ(n) ဆိုတဲ့ Formula ေလးသံုးျပီးျပန္စစ္ၾကည့္မယ္ ။ 7.103=721=1 mod 120 အိုေကျပီ။

ဟုတ္ျပီ။ ဒါဆိုရင္ 9 ဆိုတဲ့ plain text ေလးနဲ႕ encrypt / decrypt လုပ္ၾကည့္ၾကမယ္။ formula အရ 9 ဟာ m တန္ဖိုးျဖစ္တယ္ဆိုတာသိထားရပါမယ္ ။

Encryption (using public key e,n = 7,143)
Me mod n = 97 mod 143 = 48 = C

Decryption (using private key d,n =103,143)
Cd mod n = 48103 mod 143 = 9 = M

ဒီေလာက္ဆို က်ေနာ့္ Friend ေတြ RSA သေဘာတရားကိုနားလည္ျပီလို႕ယူဆပါတယ္။ က်ေနာ္ေျပာခဲ့တာေလးေတြကိုျပန္ျပီး တစ္ခုခ်င္းစမ္းသပ္မယ္ဆို ပိုျပီးနားလည္လာမွာေသခ်ာတယ္။ ဒီေတာ့ ဘယ္လိုစမ္းမွာလဲ ခ်တြက္စရာမလိုပါဘူး။ ေအာက္ကေပးထားတဲ့ Link မွာသြားတြက္ၾကည့္ပါ။ တစ္ဆင့္ခ်င္းကိုတြက္ၾကည့္လို႕ရပါတယ္။

Real World Example

Real world အေနနဲ႕ က်ေနာ္တုိ႕ “attack at dawn” ဆိုတဲ့ plain text ကိုစမ္းၾကည့္ရမယ္။ ဟုတ္ျပီ။ ပထမဆံုးဘာစလုပ္ရမလဲဆိုေတာ့ က်ေနာ္တို႕ “attack at dawn” က Ascii format ေတြျဖစ္ေနတယ္မလား။ ဒါကိုအရင္ဆံုး
Numeric ေတြေျပာင္းျပစ္ရမယ္။ ဒါမွ encrypt လုပ္လို႕ရမွာေနာ္။ အေပၚမွာ 9 ကိုလုပ္ျပထားတာမွတ္မိေသးပါတယ္။ string ကေန bit array တန္ဖိုးေတြေျပာင္းလိုက္မယ္ဆိုရင္ေတာ့ Numeric ေတြရျပီေပါ့။ 1976620216402300889624482718775150 ျဖစ္သြားမယ္။
ေအာက္မွာ Converter Link ေပးထားပါတယ္။

Key Generation လုပ္ဖို႕အတြက္ p & q တန္ဖိုးကို Prime Number ေတြ generate လုပ္ရမယ္။ ဟိုဥပမာတုန္းကလို 11 13 ေတြမရေတာ့ဘူး ။ ဒီေတာ့ Rabin-Miller primality tests ကိုသံုးျပီး generate လုပ္ၾကမယ္။ ေအာက္ကဟာေလးသံုးၾကည့္။
ကိုယ့္ဖာသာလည္း ၾကိုက္ရာရွာၾကည့္လို႕ရတယ္။

p

Code:
12131072439211271897323671531612440428472427633701410925634549312301964373042085619324197365322416866541017057361365214171711713797974299334871062829803541

q

Code:
12027524255478748885956220793734512128733387803682075433653899983955179850988797899869146900809131611153346817050832096022160146366346391812470987105415233

p နဲ႕ q ကို႕ရျပီ။ ဒါဆို n နဲ႕ ϕ(n) တန္ဖိုးကိုတြက္လို႕ရျပီ။

n

Code:
145906768007583323230186939349070635292401872375357164399581871019873438799005358938369571402670149802121818086292467422828157022922076746906543401224889672472407926969987100581290103199317858753663710862357656510507883714297115637342788911463535102712032765166518411726859837988672111837205085526346618740053

ϕ(n)

Code:
145906768007583323230186939349070635292401872375357164399581871019873438799005358938369571402670149802121818086292467422828157022922076746906543401224889648313811232279966317301397777852365301547848273478871297222058587457152891606459269718119268971163555070802643999529549644116811947516513938184296683521280

e – the public key
65537 ကိုသံုးရမယ္ ဒါကိုပဲသံုးၾကတယ္လို႕အေပၚမွာေျပာခဲ့တယ္။ ျပီးေတာ့   gcd of 1 with ϕ(n) ရွိရမယ္ေလ။

d – the private key

Code:
89489425009274444368228545921773093919669586065884257445497854456487674839629818390934941973262879616797970608917283679875499331574161113854088813275488110588247193077582527278437906504015680623423550067240042466665654232383502922215493623289472138866445818789127946123407807725702626644091036502372545139713

Encryption

1976620216402300889624482718775150e mod n

Code:
35052111338673026690212423937053328511880760811579981620642802346685810623109850235943049080973386241113784040794704193978215378499765413083646438784740952306932534945195080183861574225226218879827232453912820596886440377536082465681750074417459151485407445862511023472235560823053497791518928820272257787786

Decryption
35052111338673026690212423937053328511880760811579981620642802346685810623109850235943049080973386241113784040794704193978215378499765413083646438784740952306932534945195080183861574225226218879827232453912820596886440377536082465681750074417459151485407445862511023472235560823053497791518928820272257787786dmodn

Code:
1976620216402300889624482718775150 (which is our plaintext "attack at dawn")

Refrence : SearchSecurity , Wikipidea , doctrina , ucdenver, and googling


နည္းနည္းပ်င္းဖို႕ေကာင္းေနလိမ့္မယ္။ေနာက္တစ္ခါ ဒါနဲ႕ပတ္သတ္တဲ့ Challenge ေလးတစ္ခုေျဖၾကမယ္။ ဒါကိုမသိရင္ေတာ့ Challenge ေျဖတဲ့အခါက်ရင္ ဟိုလိုလိုဒီလိုလုိျဖစ္ေနမွာစိုးလို႕ ဒါေလးအရင္ေရးေပးလိုက္တာ။
ျပီးပါျပီ။ နားလည္ၾကပါေစလို႕ေမွ်ာ္လင့္ပါတယ္။ yeye
Best Regard , Thin Ba Shane.
Advertisements

One thought on “Digging into RSA Algorithm

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s