Skip to content

Instantly share code, notes, and snippets.

@jbrown17
Last active November 2, 2023 00:16
Show Gist options
  • Save jbrown17/05dc17ad15d1c1d739ee to your computer and use it in GitHub Desktop.
Save jbrown17/05dc17ad15d1c1d739ee to your computer and use it in GitHub Desktop.
Quick, simple implementation of RSA encryption algorithm without external libraries
import java.awt.EventQueue;
import java.io.*;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Random;
import java.util.Scanner;
/**
* Quick and dirty implementation of the RSA algorithm
* Read through main() for a breakdown on the RSA workings
*/
public class RSA {
/**
* @param args
*/
public static void main(String[] args) {
// 1. Find large primes p and q
BigInteger p = largePrime(512);
BigInteger q = largePrime(512);
// 2. Compute n from p and q
// n is mod for private & public keys, n bit length is key length
BigInteger n = n(p, q);
// 3. Compute Phi(n) (Euler's totient function)
// Phi(n) = (p-1)(q-1)
// BigIntegers are objects and must use methods for algebraic operations
BigInteger phi = getPhi(p, q);
// 4. Find an int e such that 1 < e < Phi(n) and gcd(e,Phi) = 1
BigInteger e = genE(phi);
// 5. Calculate d where d ≡ e^(-1) (mod Phi(n))
BigInteger d = extEuclid(e, phi)[1];
// Print generated values for reference
System.out.println("p: " + p);
System.out.println("q: " + q);
System.out.println("n: " + n);
System.out.println("Phi: " + phi);
System.out.println("e: " + e);
System.out.println("d: " + d);
// encryption / decryption example
String message = "Encryption test example";
// Convert string to numbers using a cipher
BigInteger cipherMessage = stringCipher(message);
// Encrypt the ciphered message
BigInteger encrypted = encrypt(cipherMessage, e, n);
// Decrypt the encrypted message
BigInteger decrypted = decrypt(encrypted, d, n);
// Uncipher the decrypted message to text
String restoredMessage = cipherToString(decrypted);
System.out.println("Original message: " + message);
System.out.println("Ciphered: " + cipherMessage);
System.out.println("Encrypted: " + encrypted);
System.out.println("Decrypted: " + decrypted);
System.out.println("Restored: " + restoredMessage);
}
/**
* Takes a string and converts each character to an ASCII decimal value
* Returns BigInteger
*/
public static BigInteger stringCipher(String message) {
message = message.toUpperCase();
String cipherString = "";
int i = 0;
while (i < message.length()) {
int ch = (int) message.charAt(i);
cipherString = cipherString + ch;
i++;
}
BigInteger cipherBig = new BigInteger(String.valueOf(cipherString));
return cipherBig;
}
/**
* Takes a BigInteger that is ciphered and converts it back to plain text
* returns a String
*/
public static String cipherToString(BigInteger message) {
String cipherString = message.toString();
String output = "";
int i = 0;
while (i < cipherString.length()) {
int temp = Integer.parseInt(cipherString.substring(i, i + 2));
char ch = (char) temp;
output = output + ch;
i = i + 2;
}
return output;
}
/** 3. Compute Phi(n) (Euler's totient function)
* Phi(n) = (p-1)(q-1)
* BigIntegers are objects and must use methods for algebraic operations
*/
public static BigInteger getPhi(BigInteger p, BigInteger q) {
BigInteger phi = (p.subtract(BigInteger.ONE)).multiply(q.subtract(BigInteger.ONE));
return phi;
}
/**
* Generates a random large prime number of specified bitlength
*
*/
public static BigInteger largePrime(int bits) {
Random randomInteger = new Random();
BigInteger largePrime = BigInteger.probablePrime(bits, randomInteger);
return largePrime;
}
/**
* Recursive implementation of Euclidian algorithm to find greatest common denominator
* Note: Uses BigInteger operations
*/
public static BigInteger gcd(BigInteger a, BigInteger b) {
if (b.equals(BigInteger.ZERO)) {
return a;
} else {
return gcd(b, a.mod(b));
}
}
/** Recursive EXTENDED Euclidean algorithm, solves Bezout's identity (ax + by = gcd(a,b))
* and finds the multiplicative inverse which is the solution to ax ≡ 1 (mod m)
* returns [d, p, q] where d = gcd(a,b) and ap + bq = d
* Note: Uses BigInteger operations
*/
public static BigInteger[] extEuclid(BigInteger a, BigInteger b) {
if (b.equals(BigInteger.ZERO)) return new BigInteger[] {
a, BigInteger.ONE, BigInteger.ZERO
}; // { a, 1, 0 }
BigInteger[] vals = extEuclid(b, a.mod(b));
BigInteger d = vals[0];
BigInteger p = vals[2];
BigInteger q = vals[1].subtract(a.divide(b).multiply(vals[2]));
return new BigInteger[] {
d, p, q
};
}
/**
* generate e by finding a Phi such that they are coprimes (gcd = 1)
*
*/
public static BigInteger genE(BigInteger phi) {
Random rand = new Random();
BigInteger e = new BigInteger(1024, rand);
do {
e = new BigInteger(1024, rand);
while (e.min(phi).equals(phi)) { // while phi is smaller than e, look for a new e
e = new BigInteger(1024, rand);
}
} while (!gcd(e, phi).equals(BigInteger.ONE)); // if gcd(e,phi) isnt 1 then stay in loop
return e;
}
public static BigInteger encrypt(BigInteger message, BigInteger e, BigInteger n) {
return message.modPow(e, n);
}
public static BigInteger decrypt(BigInteger message, BigInteger d, BigInteger n) {
return message.modPow(d, n);
}
public static BigInteger n(BigInteger p, BigInteger q) {
return p.multiply(q);
}
}
@tfkproject
Copy link

Why you add

message = message.toUpperCase();

remove that is not working. that make my string text to Upper case at all.

@jayden1f
Copy link

@tfkproject The reason for this is because the decrypting algorithm only decrypts characters that are represented by a 2 digit ASCII decimal value. When it reads in values that should actually be represented by a 3 digit ASCII value, it outputs gibberish. @jbrown17 has a workaround by just converting all text to uppercase which therefore means it will always be represented by a 2 digit ASCII value. With a bit of critical thinking you can definitely come up with a solution so that all keyboard characters of any case can be successfully decrypted. thanks for the code! @jbrown17

@PawelPabianczyk
Copy link

PawelPabianczyk commented Jun 3, 2022

Hey, if you don't want to convert message to UpperCase you should use sth like this:
BigInteger cipherMessage = new BigInteger(message.getBytes());
String restoredMessage = new String(decrypted.toByteArray());

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment