C++ Reverse Encryption

[ohJey]

I need to reverse the "encryption" done in this program

 

cloudflare is acting up so I have to post as a pastebin

 

http://pastebin.com/SyCS8CZh

 

 

[patrickjp93]

Well, this is an NP-Complete problem to do without both the original encryption keys and algorithm, so... Do you have a supercomputer?

[ohJey]

4 minutes ago, patrickjp93 said:

Well, this is an NP-Complete problem to do without both the original encryption keys and algorithm, so... Do you have a supercomputer?

Students in my class have already done it.  If you look at the program the number is encrypted by squaring it, doing modulo 90, and adding 33 to that character.  Now I need to know how to reverse it.

[MatazaNZ]

1 hour ago, ohJey said:

Students in my class have already done it.  If you look at the program the number is encrypted by squaring it, doing modulo 90, and adding 33 to that character.  Now I need to know how to reverse it.

It's just the reverse of what you did. So subtract 33, then reverse the modulo (not sure how to do this, may look it up and edit the post) then square root that number, decryption done. 

 

EDIT

There's no way to reverse a modulus operation, as all you're left with is the remainder of the division. So you won't be able to get the original number if you've used a modulus operation, unless you store the number that is being operated with 90. Which defeats the point of the encryption

[MSVSora]

Well first step ofc is ofc the -33 so we have (n - 33) rev mod 90  ^ 2

 

Now modulus is just the remainder of the divide, so we know that (n - 33) is what was left from 90 which gives us an infinite amount of possibilities

So now we have (n - 33) + (any of 90's multiples) ^ 2

 

Alright so that's simple enough right? Of course at this point I am taking the piss as you can't reverse a modulus, that's why it's used for hashing http://mathforum.org/library/drmath/view/51619.html

 

Though if you can figure out a way to reverse modulus the hackers of the world will surely thank you  

 

Edit:

 

Basically what this code does is hash the value you enter, not encrypt it a basic explanation can be found here - http://www.securityinnovationeurope.com/blog/whats-the-difference-between-hashing-and-encrypting

[MSVSora]

Which MatazaNZ added to his edit.

[ohJey]

6 hours ago, MSVSora said:

Well first step ofc is ofc the -33 so we have (n - 33) rev mod 90  ^ 2

 

Now modulus is just the remainder of the divide, so we know that (n - 33) is what was left from 90 which gives us an infinite amount of possibilities

So now we have (n - 33) + (any of 90's multiples) ^ 2

 

Alright so that's simple enough right? Of course at this point I am taking the piss as you can't reverse a modulus, that's why it's used for hashing http://mathforum.org/library/drmath/view/51619.html

 

Though if you can figure out a way to reverse modulus the hackers of the world will surely thank you  

 

Edit:

 

Basically what this code does is hash the value you enter, not encrypt it a basic explanation can be found here - http://www.securityinnovationeurope.com/blog/whats-the-difference-between-hashing-and-encrypting

yeah... I'll have to ask my teacher...  If there was a way to store the remainders after each modulus I think that would help

[MSVSora]

Just now, ohJey said:

yeah... I'll have to ask my teacher...  If there was a way to store the remainders after each modulus I think that would help

First, sorry that my previous post was rather rude, secondly, you get the remainder of the modulus after doing "n - 33", what you need is the number before the modulus or the amount that it actually divides in to. Then again that might be a part of the calculation, My response was based off what you said you needed to calculate, will take a look at the actual hash/encryption code and post back after

[ohJey]

2 minutes ago, MSVSora said:

First, sorry that my previous post was rather rude, secondly, you get the remainder of the modulus after doing "n - 33", what you need is the number before the modulus or the amount that it actually divides in to. Then again that might be a part of the calculation, My response was based off what you said you needed to calculate, will take a look at the actual hash/encryption code and post back after

it's ok no hard feelings.  I think I might understand now, but feel free to check it out 

[MSVSora]

Figured out the problem now but need to run to catch my buss, should be home in about an hour, Will post a response at that point with a solution  (The string length is the key)

 

Edit:

Getting home took longer than expected, working on it now will post back soon

[Blade of Grass]

Instead of going "backwards" to solve this problem, just solve it going forwards. 

 

I assume you know how long a student number is? Make a loop that starts with the start of the range and just calculates the code for each student. Once you've done that, store it in a table, and then use it as a loop up table of values. 

 

Edit: just realized this is for a project, therefore this method is terribly inefficient for what you want to do. 

 

I'll edit this post with a proper suggestion when I get home. 

Edited March 1, 2016 by Blade of Grass

[MSVSora]

So it took me a while but I solved it in the end, been a while since I had to work with reverse engineering like this anyway the solution looks like this

 

	string reverseEncrypt; ///reverse attempt
	cout << "\nInput the encrypted code to be reversed (copy and paste): ";
	cin >> reverseEncrypt;
	/// I'm stuck here ******************************************************************

	unsigned long long studentId = 0;
	for (unsigned int i = 0; i < reverseEncrypt.length(); ++i)
	{
		unsigned long long cur(static_cast<unsigned long long>(reverseEncrypt[i]) - 33);
		studentId = cur + ((cur / 90 + studentId) * 90);
	}

	cout << "Student Id: " << sqrt(studentId) << endl;

I changed your "reverseEncrypt" to a string instead of a int (I think thats what you had before). Other than that you should be good to go with this

 

Edit:

Updated code to look a bit better

[ohJey]

On 3/1/2016 at 0:11 PM, MSVSora said:

So it took me a while but I solved it in the end, been a while since I had to work with reverse engineering like this anyway the solution looks like this

 

	string reverseEncrypt; ///reverse attempt
	cout << "\nInput the encrypted code to be reversed (copy and paste): ";
	cin >> reverseEncrypt;
	/// I'm stuck here ******************************************************************

	unsigned long long studentId = 0;
	for (unsigned int i = 0; i < reverseEncrypt.length(); ++i)
	{
		unsigned long long cur(static_cast<unsigned long long>(reverseEncrypt[i]) - 33);
		studentId = cur + ((cur / 90 + studentId) * 90);
	}

	cout << "Student Id: " << sqrt(studentId) << endl;

I changed your "reverseEncrypt" to a string instead of a int (I think thats what you had before). Other than that you should be good to go with this

 

Edit:

Updated code to look a bit better

sorry, late reply but I got this 

 

[ohJey]

On 3/1/2016 at 0:11 PM, MSVSora said:

So it took me a while but I solved it in the end, been a while since I had to work with reverse engineering like this anyway the solution looks like this

 

	string reverseEncrypt; ///reverse attempt
	cout << "\nInput the encrypted code to be reversed (copy and paste): ";
	cin >> reverseEncrypt;
	/// I'm stuck here ******************************************************************

	unsigned long long studentId = 0;
	for (unsigned int i = 0; i < reverseEncrypt.length(); ++i)
	{
		unsigned long long cur(static_cast<unsigned long long>(reverseEncrypt[i]) - 33);
		studentId = cur + ((cur / 90 + studentId) * 90);
	}

	cout << "Student Id: " << sqrt(studentId) << endl;

I changed your "reverseEncrypt" to a string instead of a int (I think thats what you had before). Other than that you should be good to go with this

 

Edit:

Updated code to look a bit better

actually... I fixed it by adding the line

studentID=sqrt(studentID);

cout << studentID;

 

I plugged 2742724836164 into a calculator and divided by 524142 and the answer was 524142, so it wasn't doing the square root

 

anyways, thanks a lot

 

[MSVSora]

8 hours ago, ohJey said:

actually... I fixed it by adding the line

studentID=sqrt(studentID);

cout << studentID;

 

I plugged 2742724836164 into a calculator and divided by 524142 and the answer was 524142, so it wasn't doing the square root

 

anyways, thanks a lot

 

No problem, glad you got it worked out