Discuss all kind of algorithms and data structures from their mathematical and programming sides.

Moderators: Darobat, RecursiveS, Dante Shamest, Bugdude, Wizard

my teacher was talking about encryption today, and about how his algorith is "unbreakable". I wasnt paying full attention, but his "passcode" can be up to 256 characters, including spaces. If you entered the wrong characters, it gave you a message. If you entered the correct characters, not neccessarily in the correct order (they could be mixed up), it would give you a different message. he says that only brute force could be used, because there is no special encoding, and he only used randomizers, and adding, subtracting, etc. Couldn't his code be more easily broken by finding the correct keys, then de-scrambling them? In addition, due to the highly un-random nature of computers, wouldn't that be pretty easy to break? Lastly, does anyone else here think that highly advanced government computers could easily crack 256- or even 512-bit encryptions? Thanks for your time!

battousai

Posts: 279
Joined: Tue Feb 24, 2004 12:09 pm
Location: ohio

It's not in any way difficult to make an encryption algo that is "unbreakable" without brute forcing. Your teacher sounds like he doesn't know anything about cracking and how it is actually done, when you make a keygen for example the effort is in reverse engineering the validator code and from there finding how to generate a key that validates. All it requires to make an "unbreakable" encryption like that is to use a "magic number", and you can only decrypt the code by knowing this magic number. But any application for it that would work without internet access would give away the magic number and make it breakable again.

For example:
Code: Select all
`int encrypted_num = input_num*12345;`

That can't be decrypted without knowing that it is the product of the number and 12345. But a program would check if the encrypyed number was divisable by 12345 to validate it, and reverse engineering the valididator would give the magic number away.
--~~~~

Emery

Posts: 4313
Joined: Sat Mar 19, 2005 9:16 am

The only encryption algorithm that Ed can think if is one where the key is perfectly random and at least as long as the message. In that case, every possible plain text is equally likely and no form of cryptanalysis will be able to figure it out in a reasonable amount of time. This is the idea behind the one time pad, and it's theoretically unbreakable.
Subtlety is the art of saying what you think and getting out of the way before it is understood.

Posts: 381
Joined: Thu Nov 06, 2003 6:53 pm

RITZ wrote:It's not in any way difficult to make an encryption algo that is "unbreakable" without brute forcing. Your teacher sounds like he doesn't know anything about cracking and how it is actually done, when you make a keygen for example the effort is in reverse engineering the validator code and from there finding how to generate a key that validates. All it requires to make an "unbreakable" encryption like that is to use a "magic number", and you can only decrypt the code by knowing this magic number. But any application for it that would work without internet access would give away the magic number and make it breakable again.

For example:
Code: Select all
`int encrypted_num = input_num*12345;`

That can't be decrypted without knowing that it is the product of the number and 12345. But a program would check if the encrypyed number was divisable by 12345 to validate it, and reverse engineering the valididator would give the magic number away.

That's only true of private-key cryptography. In public-key cryptographic systems you can have two functions that are the inverse of each other, but knowing one of them doesn't make it obvious what the other one is.

The classic example is RSA.

Start with any number between 0 and 2027651280. For example, x=1670084462. Now compute y=(x**1933)%2027651281=1766428007. You can recover x from y by computing x=(y**5244597)%2027651281.

You can compute 1933 from 5244597 and 2027651281, but the only reasonably fast way of doing that requires knowing the factorization of 2027651281 (which is 44021 * 46061), because the trick is that (1993*5244597)%((44021-1)*(46061-1))=1, and Euler-Fermat's theorem guarantees that the two operations that we performed are the inverse of each other.

Now do the same thing using prime numbers with a couple hundred digits each. You can now use a key-code verification algorithm that takes a number, uses the (y**5244597)%2027651281 transformation and checks if the last four digits of the result are "4444". The company that created the software can generate keys very easily, because if knows 1933, but you wouldn't be able to figure out how to generate more keys by reverse-engineering the validator.

Alvaro
Moderator

Posts: 5185
Joined: Mon Sep 22, 2003 4:57 pm
Location: NY, USA

ok, I don't feel like turning on my scanner to show you his flowchart, but Im gonna try to explain it. I found all this out after last night's post. Sorry it was so hurried.
The user enters a password, up to 256 characters. At 8 bits per character, this is pretty big. Then, they are basically lined up in rows of 32, and added together, to create a 512-bit 'checksum'. In the case of passwords that have a number of characters that aren't a power of 32, 0's are used to pad. Then, and this part I don't fully understand, the resulting key (the checksum) is seeded into the randomizer. It uses the plaintext file, 2 randomizers, and the checksum to encrypt the plaintext file. It ends up with the file being split up into blocks of I believe 32 bite each. The first block has only been affected by the checksum itself, all other blocks have been affected by the checksum, the randomizers, the original file...I dunno, its confusing.
His program checks for the checksum first (so it doesnt have to perform all operations on an inncorectly-entered password. It tells you if the checksum is wrong (based on the keys. basically, if you have the right characters(out of the whole 256 ascii characters, btw), but the wrong password, it will tell you. If you have the wrong password all together (checksum is not correct), then it gives you a different message.
Is this a strong encryption algorithm? I may be wrong, but he says that having the checksum only reduces the number of possible guesses by 2^8, so 2^504. Is that correct? Also, he says that other then brute-forcing, there is no way to crack his password. Is this true? Isn't the password a weakness of his encryption?
Well, thank you for your time. Sorry to have just re-appeared suddenly throwing out crazy questions.

battousai

Posts: 279
Joined: Tue Feb 24, 2004 12:09 pm
Location: ohio