Rivest-Shamir-Adleman [C++]

RSA is an algorithm for public-key cryptography that is based on the presumed difficulty of factoring large integers, the factoring problem. RSA stands for Ron Rivest, Adi Shamir and Leonard Adleman, who first publicly described it in 1978. A user of RSA creates and then publishes the product of two large prime numbers, along with an auxiliary value, as their public key. The prime factors must be kept secret. Anyone can use the public key to encrypt a message, but with currently published methods, if the public key is large enough, only someone with knowledge of the prime factors can feasibly decode the message. Whether breaking RSA encryption is as hard as factoring is an open question known as the RSA problem.

 

RSA Algorithm Example

  • Choose p = 3 and q = 11
  • Compute n = p * q = 3 * 11 = 33
  • Compute φ(n) = (p - 1) * (q - 1) = 2 * 10 = 20
  • Choose e such that 1 < e < φ(n) and e and n are coprime. Let e = 7
  • Compute a value for d such that (d * e) % φ(n) = 1. One solution is d = 3 [(3 * 7) % 20 = 1]
  • Public key is (e, n) => (7, 33)
  • Private key is (d, n) => (3, 33)
  • The encryption of m = 2 is c = 27 % 33 = 29
  • The decryption of c = 29 is m = 293 % 33 = 2

//Code developed by: Vishwanath Sarang
#include
#include
 
int gcd(int a, int b)
{   int temp;
while(b!=0)
{
temp = b;
b = a % b;
a = temp;
}
return a;
}
 
int powMod(int base, int exp, int modulus)
{
int accum=1, i=0, basepow2=base;
// Look at each bit of exp, low to high
while ((exp>>i)>0)
{
// If the exponent bit of exp is 1 multiply by base^(2^i)
if(((exp>>i) & 1) == 1)
{
accum = (accum*basepow2) % modulus;
};
// In any event compute base^(2^i) for next i value
basepow2 = (basepow2*basepow2) % modulus;
i = i+1;
};
return accum;
}
 
int eeaD(int a, int b){
 
// keeps track of the initial value of a.
int a0 = a;
 
// temporary variables
int x = 1;
int v = 1;
 
int y = 0;
int u = 0;
 
int q;  int r; int newu; int newv;
 
while (b != 0)
{
q = floor(a/b);
r = a % b;
 
a = b;
b = r;
 
newu = x - q*u;
newv = y - q*v;
 
x = u;
y = v;
 
u = newu;
v = newv;
 
}
 
 
if (y > 0)
{
return y;
}
 
else
{
return y + a0;
}
 
 
 
// document.form3.Dfield.value = "x = " + x + " and y = " + y;
 
 
}
 
int "u4ej1_7" class="u4ej1">encrypt(int message, int pubkey, int n){
 
return powMod(message, pubkey, n);
 
}
 
int decrypt(int prikey, int msg, int n){
 
return powMod(msg, prikey, n);
 
}
 
int main()
{       int p, q, n, phi, pubk, m, e, flag=1;
int gcdpq;
 
while(flag==1)
{cout<<"Enter the value of P and Q which are relatively u4ej1_5" class="u4ej1">prime.\nThat is, their GCD is 1\n";
cout<<"Enter the value of P which is relatively prime\n";
cin>>p;
cout<<"Enter the value of Q which is relatively prime";
cin>>q;
gcdpq = gcd(p,q);
if (gcdpq != 1)
{
cout<<"P and Q are not relatively prime.  Their GCD is "<".";
flag=1;
}
else {flag=0;}
};
 
cout<<"Calculating N...\n";
n=p*q;
cout<<"N = "<"\n";
cout<<"Calculating Phi...";
phi=(p-1)*(q-1);
cout<<"Phi = "<"\n";
pubk = 2;
 
while( gcd(pubk, phi) !=1)
{
pubk++;
};
int prik = eeaD(phi, pubk);
 
cout<<"Enter a message to be encrypted\n";
cin>>m;
cout<<"Encrypted message is "<"\n";
 
cout<<"Enter a message to be decrypted\n";
cin>>e;
cout<<"Decrypted message is "<"\n";
getch();
return 0;
 
}
 
 
/*OUTPUT
Enter the value of P and Q which are relatively prime.
That is, their GCD is 1
Enter the value of P which is relatively prime
70
Enter the value of Q which is relatively prime19
Calculating N...
N = 1330
Calculating Phi...Phi = 1242
Enter a message to be encrypted
1210
Encrypted message is 90
Enter a message to be decrypted
90
Decrypted message is 1210
*/
دانلود سورس این الگوریتم به زبان c++
http://milindmathur.com/RSA512.zip
سورس الگوریتم رمزگذاری RSA به زبان HTML و PHP
http://www.phpclasses.org/package/4121-PHP-Encrypt-and-decrypt-data-with-RSA-public-keys.html
یک سایت دیگر سورس همین برنامهالگوریتم RSA به زبان C++ به شیوه ای دیگر
http://stackoverflow.com/questions/9406840/rsa-encrypt-decrypt

دانلود پاور پوینت مقاله در رابطه با الگوریتم RSA به زبان انگلیسی
http://ewubd.edu/~allayear/lecture/The%20RSA%20Algorithm.ppt

جهت اجرای این الگوریتم به صورت عملی و تست ان به سایت های زیر مراجعه کنید
تست این الگوریتم به صورت انلاین

سایت اول
http://logos.cs.uic.edu/340%20Notes/rsa.html

سایت دوم
http://www.strangeattractor.ca/RSAdemo.html
سایت سوم
http://tizhoosh.uwaterloo.ca/Teaching/RSA.htm
سایت چهارم
https://www.cs.drexel.edu/~introcs/Fa11/notes/10.1_Cryptography/RSA_Express_EncryptDecrypt.html
سایت پنجم
 به همراه سورس کد برنامه PHPو تست آنلاین برنامه
http://courses.gdeyoung.com/pages/encryption/rsa.php
این هم دانلود نرم افزاری در زمینه الگوریتم RSA
دانلود نرم افزار

SolidRSA 1.0.0.0

این هم یک نرم افزار دیگر که نمونه ای از الگوریتم RSA است
نرم افزار رمز گذاری به روش RSA
نرم افزار

Total Encryption 1.2

این هم یک نرم افزار دیگر

RSA-Tools 1.3

این هم یک نرم افزار دیگر

RSAmake 1.1.0 Beta

این هم یک نرم افزار دیگر

RSAVisualWin


Click here to download the Windows version