post image

الگوریتم رمزگذاری RSA

29 اردیبهشت 99

رمز گذاری RSA یک شیوه رمز گذاری اطلاعات هست که امروزه کاربرد زیادی در تمامی پروتکل‌های ایمن از جمله TLS دارد.

RSA به‌طور کلی از دو کلید تشکیل می‌شود. کلید عمومی و کلید خصوصی. کلید، عدد صحیح ثابتی است که در محاسبات رمزنگاری استفاده می‌شود. کلید عمومی برای همه معلوم بوده و برای رمزنگاری پیام استفاده می‌شود. اما پیام رمزنگاری شده فقط توسط کلید خصوصی باز می‌شود. در بیان دیگر همه می‌توانند یک پیام را رمزنگاری کنند اما فقط صاحب کلید خصوصی است که می‌تواند پیام را باز کند و بخواند.

هر چند از لحاظ ریاضی کلیدهای عمومی و خصوصی با یکدیگر ارتباط دارند اما تقریباً محال است که کسی بتواند حتی با تجیهزات پیشرفته و صرف وقت زیاد با داشتن یکی از کلیدها، دیگری را تشخیص دهد. تقریباً می‌توان گفت که با توجه به سطح دانش کنونی و سیستم‌های نرم‌افزاری موجود، الگوریتم رمزنگاری و ارتباط میان کلیدها غیرقابل شکستن است.

RSA مبتنی بر توان‌رسانی پیمانه‌ای است یعنی بر اساس نظریه اعداد و قضیه هم‌نهشتی اعداد اطلاعات را رمزگذاری می‌کند، و برای این کار از طبیعی خیلی بزرگ استفاده می‌کند.

شیوه عملکرد

در ابتدا دو عدد p و q به صورت تصادفی انتخاب می‌شوند.

حاصل ضرب این دو عدد را n در نظر می‌گیریم و با توجه به آن تابع فی را تعریف می‌کنیم.

phi(n) = (p – ۱)(q – ۱)

یک عدد مثل e انتخاب می‌کنیم به طوری که نسبت به phi اول باشد و از ۱ کوچک تر باشد.

عدد e را به عنوان کلید عمومی منتشر می‌کنیم

عدد d را طوری میابیم که :


عدد d را به عنوان کلید خصوصی نگه می‌داریم.

کلید عمومی تشکیل می‌شود از:

  • عدد n (عدد مشترک)
  • عدد e (عدد عمومی)

کلید خصوصی تشکیل می‌شود از:

  • عدد n (عدد مشترک)
  • عدد d (عدد خصوصی)

باقی مانده ضرب ۲ عدد d و e نسبت به phi برابر با ۱ است و این رابطه‌ی زیر برای هر عدد طبیعی k برقرار است :‌

de = ۱ + k(phi)

رمزنگاری پیام

فرض کنید می‌خواهید پیامی را رمزنگاری کرده و به فردی دیگر بفرستید. شما می‌بایست کلید عمومی آن فرد را از او دریافت کرده و پیام خود را در قالب یک عدد (m) در بیاورید به‌طوری‌که این فرایند برگشت‌پذیر بوده و عدد شما از n کوچک‌تر باشد. بدیهی است اگر پیام بزرگ‌تر از حد معمول باشد آن را در بسته‌های جداگانه می‌فرستیم. شما اکنون عدد C را محاسبه می‌کنید به‌طوری‌که


حال اگر پیام رمزنگاری شدهٔ C را برای یک کلاینت بفرستید او می‌تواند توسط کلید خصوصی اش آن را رمزگشایی کند و بفهمد.

رمزگشایی پیام

فرض کنید شما پیام رمزنگاری شدهٔ C را دریافت کرده‌اید و کلید خصوصی خود را در دسترس دارید. حال شما می‌توانید عدد m را که معادل پیام اصلی است از C ،n، و d بازیابی کنید.


نمونه کد پیاده سازی الگوریتم RSA به زبان Java

import java.math.BigInteger;
import java.security.SecureRandom;
 

public class RSA {
 private final static BigInteger one = new BigInteger("۱");
 private final static SecureRandom random = new SecureRandom();

 private BigInteger privateKey;
 private BigInteger publicKey;
 private BigInteger modulus;

 // generate an N-bit (roughly) public and private key
 RSA(int N) {
 BigInteger p = BigInteger.probablePrime(N/۲, random);
 BigInteger q = BigInteger.probablePrime(N/۲, random);
 BigInteger phi = (p.subtract(one)).multiply(q.subtract(one));

 modulus = p.multiply(q); 
 publicKey = new BigInteger("۶۵۵۳۷"); // common value in practice = ۲^۱۶ + ۱
 privateKey = publicKey.modInverse(phi);
 }


 BigInteger encrypt(BigInteger message) {
 return message.modPow(publicKey, modulus);
 }

 BigInteger decrypt(BigInteger encrypted) {
 return encrypted.modPow(privateKey, modulus);
 }

 public String toString() {
 String s = "";
 s += "public = " + publicKey + "\n";
 s += "private = " + privateKey + "\n";
 s += "modulus = " + modulus;
 return s;
 }
 
 public static void main(String[] args) {
 int N = Integer.parseInt(args[۰]);
 RSA key = new RSA(N);
 StdOut.println(key);
 
 // create random message, encrypt and decrypt
 BigInteger message = new BigInteger(N-۱, random);

 //// create message by converting string to integer
 // String s = "test";
 // byte[] bytes = s.getBytes();
 // BigInteger message = new BigInteger(bytes);

 BigInteger encrypt = key.encrypt(message);
 BigInteger decrypt = key.decrypt(encrypt);
 StdOut.println("message = " + message);
 StdOut.println("encrypted = " + encrypt);
 StdOut.println("decrypted = " + decrypt);
 }
}
به این شیوه رمزگذاری end۲end نیز می‌گوییم چون در هر بار اتصال بین دو کلاینت کلید‌ خصوصی تغییر می‌کند و پیام‌ها با کلید جدیدی رمزنگاری می‌شود. این کار امنیت ارتباط را حدوداً تا ۹۹٫۵٪ بالا می‌برد.

منتشر شده توسط