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.

Longarmx · October 15, 2014, 2:34am

This is why they use one-time keys.

lcass · October 15, 2014, 3:28pm

Still from that data , ie you intercept it you can obtain the password and login sent. Changing the key doesnt change the data that they sent.

pjt33 · October 15, 2014, 3:38pm

Is there a TL;DR version which just includes the maths and none of the UI or debug output?

That said, there are known weaknesses in the simple version of RSA which is presented in introductory number theory lessons.

lcass · October 15, 2014, 4:09pm

Sure ill just create the code in a sec and send you the pastebin.

Yes I can see the situation in those links however the point to this is that no matter how hard it is to decrypt if you are able to recover data at all you are closer to the solution , so for instance if the data was pre encrypted with another key then patterns can be seen in the code allowing for it to be checked over. As said if it uses multiple layers of encryption its more difficult this just removes the main level. With something such as padding it only makes the data difficult to interpret when it is in the encrypted form outside of that the padding is easy to spot. I think that main thing that needs to happen now is dynamic cryptography , where the data is manipulated so that it looks like something that its not such as hiding a simple encryption as a series of hashes.

In bank security it is most likely that all data is hashed within the client and then RSA encrypted meaning that only with access to the server would you be able to confirm it.However all other information would have to be sent in standard text , you would be able to monitor what they were doing.

lcass · October 15, 2014, 4:19pm

http://pastebin.java-gaming.org/3f9d315161d11

pjt33 · October 15, 2014, 6:55pm

Ok, I see what the problem is. You’re not even attacking naive RSA: you’re attacking RSA used in ECB mode on a block size of 8 bits. This attack has real world value only against a teenager who has heard of RSA but doesn’t understand it.

lcass · October 15, 2014, 8:17pm

So give me a form of RSA encryption that is stronger. I am interested in this and want to see what you are talking about.

Longarmx · October 15, 2014, 10:36pm

I don’t know too much about RSA myself, but I will give it a shot.

The thing that makes any encryption strong is that you encrypt the entire message at once. What you’re doing here is encrypting each letter separately, into uniform blocks of numbers. This makes it very easy to decrypt each letter separately using a rainbow table. When you encrypt the entire message at once though, you can’t just decrypt each letter separately. That’s what makes it so strong.

A good example of this I think is hashing. If one bit changes, then the entire hash is different. This is what makes it so hard to reverse the process.

pjt33 · October 16, 2014, 8:43am

[quote=“lcass,post:8,topic:51477”]
The standard approach is to encrypt a key for a symmetric algorithm such as AES. So that’s one RSA message, containing a 256-bit key padded with OAEP.

lcass · October 16, 2014, 3:57pm

Ok , well from longarmx I took the idea and have begun making the encryption so that the data is not the int value of the char so A 65 , if I was sending ABCD the data I would encrypt would be 65666768 , which would be decoded , I can see how this is exponentially more secure, you would need to perform 65666768 combinations with a total of 99^4 different solutions to value within 100 , if padding was added as you said and then the data was encrypted in a way to make it as difficult as possible , such as a password say password which would be 11297115115119111114100 this is then put into the RSA code instead of each character, it is then dissected upon decryption where each character is equal to (int)(data / (n * 1000)) (I think), where N is the character position in the word , its maximum can be resolved to string.length / 3(each has a max of 255 so you can divide). Still there are flaws in this , if the data is short say Ok or a simple word then the decryption could take seconds due to the combinations , if some complex math was used knowing the logic behind how it works the value could be resolved. Thanks for the info.

CodeHead · October 16, 2014, 7:12pm

Good encryption techniques live and die by the rule that even if a method of encryption is known, the encrypted data should still remain secure. If this were not the case then public review of encryption techniques would always invalidate their effectiveness. If you can resolve the value based on what you’ve said either a)the encryption method is seriously flawed, or b)your testing methods are flawed.

lcass · October 16, 2014, 9:37pm

What I mean was if the length of the data you were transmitting using my method was small enough a simple pc could crack it , sending 8 encoded chars per encryption would yield 255^8 different combinations that would need to be tried. If you did this with a bigger number such as 64 bytes then thats 255^64 which would be horrendous to attempt to crack , the only ,method for it would be brute force.