ആർ.എസ്.എ. അൽഗൊരിതം

ഇംഗ്ലീഷ് വിലാസം

https://ml.wikipedia.org/wiki/RSA_(algorithm)

RSA

General
Designers	Ron Rivest, Adi Shamir, and Leonard Adleman
First published	1977
Certification	PKCS#1, ANSI X9.31, IEEE 1363
Cipher detail
Key sizes	1,024 to 4,096 bit typical
Rounds	1
Best public cryptanalysis
General number field sieve for classical computers; Shor's algorithm for quantum computers. A 829-bit key has been broken.

ഒരു പബ്ലിക് കീ ക്രിപ്റ്റോഗ്രഫി അൽഗൊരിതമാണ് ആർ.എസ്.എ. അൽഗൊരിതം. ഇതുണ്ടാക്കിയത് റോൺ റിവസ്റ്റ് (Ron Rivest), അഡി ഷമീർ (Adi Shamir), ലെനാർഡ് അഡ്ല്മാൻ (Leonard Adleman) എന്നിവരാണ്. ഇവരുടെ പേരുകളുടെ ആദ്യാക്ഷരങ്ങളിൽ നിന്നാണ് ഈ അൽഗൊരിതത്തിന് അർ.ഏസ്.ഏ (RSA) എന്ന പേര് വന്നത്. വലിയ സംഖ്യകളുടെ ഘടകങ്ങൾ കണ്ടെത്തുന്നത് അത്ര എളുപ്പമല്ല എന്നതാണ് ഈ അൽഗൊരിതത്തിന്റെ കേന്ദ്രതത്ത്വം. ഏത് പബ്ലിക് കീ എൻക്രിപ്ഷൻ രീതിയിലേതും പോലെ ഇവിടെയും ഒരു പബ്ലിക് കീയും ഒരു പ്രൈവറ്റ് കീയുമുണ്ടാകും. പബ്ലിക് കീ രണ്ട് അഭാജ്യസംഖ്യകളുടെ ഗുണനഫലവും (n) ഒരു എൻക്രിപ്ഷൻ ഘാതവും (e) ചേർന്ന ക്രമജോഡിയായിരിക്കും (n,e). n ഉം ഡീക്രിപ്ഷൻ ഘാതമായ d യും ചേർന്ന ക്രമജോഡിയായ (n,d) ആണ് പ്രൈവറ്റ് കീ.

ഉദാഹരണം

RSA അൽഗോരിതം മൂന്ന് പ്രക്രിയകൾ അടങ്ങുന്നു കീ ഉത്പാദനം,എൻക്രിപ്ഷൻ,ഡീക്രിപ്ഷൻ.

കീ ഉല്പാദനം

• രണ്ട് അഭാജ്യസംഖ്യകൾ (p,q) എടുക്കുക. p= 29 ഉം q = 31 ഉം ആണെന്ന് വയ്ക്കുക
• ഇവയുടെ ഗുണനഫലമാണ് പബ്ലിക് കീയുടെ ഒരു ഭാഗമായ n. n = p * q = 29 * 31 = 899
• n ന്റെ ടോഷ്യന്റ് ഫലനമായ φ(n) കണ്ടെത്തുക. φ(n) = φ(899) = φ(29*31) = 28*30 = 840
• എൻക്രിപ്ഷൻ ഘാതമായ e തിരഞ്ഞെടുക്കുക. e തിരഞ്ഞെടുക്കുമ്പോൾ രണ്ട് കാര്യങ്ങൾ ഉറപ്പുവരുത്തേണ്ടതുണ്ട്. 1 < e < φ(n) ആയിരിക്കണം. e,φ(n) എന്നിവ സഹ-അഭാജ്യമായിരിക്കുകയും വേണം. ഉദാഹരണമായി, e=11 എന്നെടുക്കാം. 11 ന്റെയും 840 ന്റെയും ഉത്തമ സാധാരണ ഘടകം 1 ആയതിനാൽ അവ സഹ-അഭാജ്യമാണ്
• $U_{\phi (n)}$ എന്ന ഗ്രൂപ്പിൽ e യുടെ വിപരീത അംഗമായ d ആണ് ഡീക്രിപ്ഷൻ ഘാതം. അതായത് e * d ≡ 1 (mod φ(n)) ആയിരിക്കണം. d, e എന്നിവയുടെ ഗുണനഫലത്തെ φ(n) കൊണ്ട് ഹരിച്ചാൽ ശിഷ്ടം 1 ലഭിക്കണം എന്നർത്ഥം. യൂക്ലിഡിന്റെ എക്സ്റ്റെൻഡഡ് അൽഗൊരിതം ഉപയോഗിച്ചാൽ d കണ്ടുപിടിക്കാം. ഇവിടെ d = 611 എന്ന് ലഭിക്കുന്നു (611 * 11 = 6721 ≡ 1 mod 840)
• അതായത്, പബ്ലിക് കീ (899,11) ആണെന്നും പ്രൈവറ്റ് കീ (899,611) ആണെന്നും ലഭിക്കുന്നു.

എൻക്രിപ്ഷൻ

ഇനി ഇത് വച്ച് എങ്ങനെ എൻക്രിപ്ഷൻ ചെയ്യുന്നു എന്ന് നോക്കാം. ഉദാഹരണത്തിന് ഒരു കമ്പ്യൂട്ടറിൽ നിന്ന് മറ്റൊരു കമ്പ്യൂട്ടറിലേക്ക് "A" എന്ന അക്ഷരം എൻക്രിപ്റ്റ് ചെയ്ത് അയക്കണമെന്ന് വച്ചോ. ഇതിന്റെ ASCII വാല്യു (ഡെസിമൽ) 65 ആണ്.

• 65^e mod n = 65¹¹mod 899 = 168 (11 എൻക്രിപ്ഷൻ ഘാതവും, 899 പബ്ലിക് കീയിലെ മോഡ്യുലസുമാണെന്നോർക്കുക)

65 നെ എൻക്രിപ്റ്റ് ചെയ്തതിന്റെ ഫലമായ 168 ആണ് മറ്റേ കമ്പ്യൂട്ടറിലോട്ട് അയക്കുക.

ഡീക്രിപ്ഷൻ

സ്ന്ദേശം ലഭിക്കുന്ന കമ്പ്യൂട്ടർ 168 നെ ഇപ്രകാരം ഡീക്രിപ്റ്റ് ചെയ്യുന്നു.

• 168^d mod n = 168⁶¹¹ mod 899 = 65 ( 611 നമ്മുടെ ഡീക്രിപ്ഷൻ ഘാതവും , 899 പബ്ലിക് കീയും ആണെന്നോർക്കുക)

സുരക്ഷ

ഈ സന്ദേശത്തെ മറ്റേതെങ്കിലും തല്പരകക്ഷിക്ക് (ഉദാ : ഗവണ്മെന്റ് ഇന്റലിജൻസ് ഏജൻസികൾ) പൊളിച്ച് (break) മെസ്സേജ് എന്തെന്ന് മനസ്സിലാക്കണമെങ്കിൽ പബ്ലിൿ കീയായ 899 യിൽ നിന്ന് അതിന്റെ ഫാക്റ്ററുകളായ ആ രണ്ട് അഭാജ്യസംഖ്യകൾ കിട്ടണം. ഇതിന് ഒരു മാർഗ്ഗമാണ് ബ്രൂട്ട് ഫോഴ്സ് ആക്രമണം. എന്നാൽ ബ്രൂട്ട് ഫോഴ്സ് ആക്രമണങ്ങൾ വലിയ സംഖ്യകൾക്ക് വളരെ സമയമെടുക്കുന്നവയാണ്. കൂടുതൽ കാര്യക്ഷമമായ ഗൂഢശാസ്ത്രആക്രമണങ്ങളും ഉണ്ടെങ്കിലും ഇന്നത്തെ നിലയിൽ 1000 ബിറ്റുകൾക്ക് മുകളിലുള്ള, നല്ല രീതിയിൽ തിരഞ്ഞെടുക്കപ്പെട്ട ആർ.എസ്.എ. കീകൾ ക്രാക്ക് ചെയ്യുന്നത് അസാധ്യമെന്നുതന്നെ പറയാം.