RSA direct bypass

lcass · October 14, 2014, 4:52pm

So , I have sort of came up with a way to directly bypass the RSA encryption with relatively little computational effort. So in the form of a MITM attack (man in the middle) where all he knows is the public key , how do you effectively decrypt there message? you would assume you would need to know the private key in order to decrypt using the function encrypted_var^privatekey mod sum_of_primes. However that takes effort , a lot of effort , especially with the banks using 2048bit (671 digit long) codes. So that obviously wont work unless you have a couple of super computers to hand however what if you pregenerate the keyset IE you have monitored the traffic and you know what the public key is , you then take this and you apply it to every character in the ascii key set. so a b c d e f g on and on until you have the value for each , during the transmission you then check this against the message they are sending and you can effectively decrypt using fairly little computational effort, if they are sending a relatively long message say a few thousand characters like a resume then you will use less effort calculating the values than they did actually encrypting their data.
So using my little RSA algorithm , it doesnt use very large numbers as I didnt want to use biginteger however it is still viable to use to test.
Here is the code for calculating an RSA encryption from the given keys:
[spoiler]

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.math.BigInteger;
import java.util.Random;

import javax.swing.JOptionPane;
import javax.swing.filechooser.FileFilter;

public class Encryptor {
	

	public Encryptor() {
		long[] key = new long[4];
		boolean newkeys = JOptionPane.showConfirmDialog(null,
				"Generate new keys?") == JOptionPane.YES_OPTION;
		if (newkeys) {
			key = calculate_key(generateprimelong(), generateprimelong());
			JOptionPane.showMessageDialog(null, "Your public key is: " + key[0] + "," + key[1]);
			JOptionPane.showMessageDialog(null, "Your private key is: " + key[2] + "," + key[3]);
			
		}
		else{
		
			
		}
		if (JOptionPane.showConfirmDialog(null,
				"Are you decrypting?")== JOptionPane.YES_OPTION) {
			if(!newkeys){
				String privatekey = JOptionPane.showInputDialog("Please enter you private key in the form a,b");
				String[] pks = privatekey.split(",");
				key[2] = Long.parseLong(pks[0]);
				key[3] = Long.parseLong(pks[1]);
			}
			String decryptlocation = JOptionPane
					.showInputDialog("Please enter the file location of your encrypted text file");
			try {
				decrypt(key[2],key[3],read(decryptlocation));
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
		} else {
			if(!newkeys){
				String publickey = JOptionPane.showInputDialog("Please enter your public key in the form a,b");
				String[] pls = publickey.split(",");
				key[0] = Long.parseLong(pls[0]);
				key[1] = Long.parseLong(pls[1]);
			}
			String fileloc = JOptionPane
					.showInputDialog("Enter the location of your unencrypted text file");
			try {
				String data = readstring(fileloc);
				encrypt(key[0],key[1],data);

			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
		}
	}

	public static void main(String[] args) {
		new Encryptor();

	}

	private static Random r = new Random();

	public static long generateprimelong() {

		boolean testing = true;

		while (testing) {
			long num = Math.abs(r.nextLong()) / 900000000000000l;
			if (!isprime(num)) {
				continue;
			}
			testing = false;
			return num;

		}
		return 0l;
	}

	public static boolean isprime(long n) {
		if (n <= 3) {
			if (n <= 1) {
				return false;
			} else {
				return true;
			}
		}
		if (n % 2 == 0 || n % 3 == 0) {
			return false;
		}
		for (int i = 5; i < Math.sqrt(n) + 1; i += 6) {
			if (n % i == 0 || n % (i + 2) == 0) {
				return false;
			}
		}
		return true;
	}

	public static int generateprimeshort(int max) {
		boolean testing = true;

		while (testing) {
			int num = Math.abs(r.nextInt(max));
			if (!isprime(num)) {
				continue;
			}
			testing = false;
			return num;

		}
		return 0;
	}

	public long[] calculate_key(long P, long Q) {
		long n = P * Q;
		long tonient_n = (P - 1) * (Q - 1);
		long e = generateprimeshort(Math.abs((int) (Math.sqrt(n))));
		long d = findInverse(e, tonient_n);
		long[] keys = new long[4];
		keys[0] = n;
		keys[2] = n;
		keys[1] = e;
		keys[3] = d;
		// encrypt(n, e,
		// "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789");
		return keys;
	}

	public static long findInverse(long a, long b) {
		long calculate = b;
		long x = 0, y = 1, lastx = 1, lasty = 0;
		while (b != 0) {
			long quotient = a / b;

			long temp = a;
			a = b;
			b = temp % b;

			temp = x;
			x = lastx - quotient * x;
			lastx = temp;

			temp = y;
			y = lasty - quotient * y;
			lasty = temp;
		}

		// int[] coefficients = {lastx, lasty, a};
		return calculate + lastx;
	}

	public void encrypt(long a, long b, String information) {
		long[] value = new long[information.length()];

		for (int i = 0; i < information.length(); i++) {
			char letter = information.charAt(i);
			int lettercode = letter;
			value[i] = powmod(lettercode, b, a);
		}
		try {
			write(value);
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
	public void decrypt(long a , long b , long[] data){
		String datastring= "";
		for(int i = 0; i < data.length;i++){
			long value = powmod(data[i],b,a);
			System.out.println(value);
			datastring += (char)value;
		}
		try {
			writestring(datastring);
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		
		
	}

	public static long powmod(long base, long exponent, long modulus) {
		if (exponent < 0)
			throw new IllegalArgumentException("exponent < 0");
		long result = 1;
		while (exponent > 0) {
			if ((exponent & 1) != 0) {
				result = (result * base) % modulus;
			}
			exponent >>>= 1;
			base = (base * base) % modulus;
		}
		return result;
	}

	public static void write(long[] content) throws IOException {
		File file = new File("Encrypted.txt");
		if (!file.exists()) {
			file.createNewFile();
		}

		FileWriter fw = new FileWriter(file.getAbsoluteFile());
		BufferedWriter bw = new BufferedWriter(fw);
		for (int i = 0; i < content.length; i++) {
			try {
				bw.write(Long.toString(content[i]) + ";");
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
		}
		bw.close();

	}
	public static void writestring(String content) throws IOException {
		File file = new File("unencrypted.txt");
		if (!file.exists()) {
			file.createNewFile();
		}

		FileWriter fw = new FileWriter(file.getAbsoluteFile());
		BufferedWriter bw = new BufferedWriter(fw);
		bw.write(content);
		bw.close();

	}

	public static long[] read(String location) throws IOException {
		File file = new File(location);

		if (!file.exists()) {
			System.out.println("NO FILE LOCATED");
			return null;
		}
		FileReader fr = new FileReader(file.getAbsoluteFile());
		BufferedReader br = new BufferedReader(fr);
		String filedata = br.readLine();
		String[] info = filedata.split(";");
		long[] data = new long[info.length];
		for (int i = 0; i < info.length; i++) {
			data[i] = Long.parseLong(info[i]);
		}
		return data;
	}

	public static String readstring(String location) throws IOException {
		File file = new File(location);

		if (!file.exists()) {
			return null;
		}
		FileReader fr = new FileReader(file.getAbsoluteFile());
		BufferedReader br = new BufferedReader(fr);
		String filedata = br.readLine();
		return filedata;
	}

}

[/spoiler]
Here are the keys it generated for me public key: modulo = 4127353, exponent = 1193 private key: inverse modulo of the totient of n and e = 3853577.
So ill encrypt some data , just a simple sentence.

Hi there my pseudonym is lcass <- hazzah , so what does this code output.

tada:

110284;3066158;2777967;1857537;3770054;2342914;1419964;2342914;2777967;2041712;179304;2777967;2630803;1377978;2342914;2399661;3956477;461248;3312036;179304;2041712;2777967;3066158;1377978;2777967;1251139;133099;3923355;1377978;1377978;

So the algorithm works , it provides a seemingly impossible to solve output with only the public key known. The code to crack this is horrendously simple , a primary school student could learn to do write it.

So whats the output from my software (currently)
[spoiler]

[/spoiler]
checking it the output from my RSA “H” is the same as the interpreter.
Now to get it to decrypt an entire message.

And whats the output?

Hi there my pseudonym is lcass
Here is the cracking code.

[spoiler]


import javax.swing.JOptionPane;
public class RSA {
	int[] ASCII_CHAR_SET = new int[256];//I dont know the actual length so just have it like this
	char[] DATA_COMPARE = new char[256];//the data to reference , random access abit easier than char casting
	public RSA(){
		System.out.println("RSA HACKER STARTED");
		String key = JOptionPane.showInputDialog("What is the public key , enter in the form n,e");
		String[] public_key = key.split(",");//split string where public_key[0] = n and public_key[1] = e
		System.out.println("Key accepted , preparing to generate keyset");
		//convert both to their integer counterparts
		int sum_n = Integer.valueOf(public_key[0]);
		int exponent = Integer.valueOf(public_key[1]);
		//perform the key set generation
		for(int i =0; i < ASCII_CHAR_SET.length;i++){
			ASCII_CHAR_SET[i] = powmod(i,exponent,sum_n);
			char current = (char)i;//should be able to convert from int to char
			DATA_COMPARE[i] = current;//fairly simple assign the character to this
			System.out.println(ASCII_CHAR_SET[i] + " " + current);
		}
		String data = JOptionPane.showInputDialog("What is the data you wish to decrypt");
		String[] seperated_data = data.split(";");
		String output = "";
		for(int i = 0;i < seperated_data.length;i++){
			int value = Integer.valueOf(seperated_data[i]);
			for(int j = 0;j < ASCII_CHAR_SET.length;j++){
				if(ASCII_CHAR_SET[j] == value){
					output+= DATA_COMPARE[j];
					
					break;
				}
			}
		}
		System.out.println(output);
	}
	public static int powmod(long base, long exponent, long modulus) {
		if (exponent < 0)
			throw new IllegalArgumentException("exponent < 0");
		long result = 1;
		while (exponent > 0) {
			if ((exponent & 1) != 0) {
				result = (result * base) % modulus;
			}
			exponent >>>= 1;
			base = (base * base) % modulus;
		}
		return (int)result;
	}//very large numbers so a very annoying method must be required.
	public static void main(String[] args){
		new RSA();//static tags become annoying after some time
	}
}

[/spoiler]

Enjoy.