A Question About Encryption

[zanco]

This question is particularly aimed to Hooman, since he is the one who stirred my curiosity in the domain.

I won't turn around the bush, so : How was your cypher encrypted (not that I want you to give the solution or something)?  If a key is used, how is it selected/generated?  :heh:    

[Hooman]

Yes..., two very relavent questions.


1) The key. (Unfortunately, this probably won't help you   )

Some key word or key phrase is selected. For instance take "OUTPOST UNIVERSE FORUMS". Now, remove all the spacing and duplicate letters. You end up with "OUTPSNIVERFM". Now we want to add all the rest of the letters of the alphabet that are currently missing at the end of this. Only, instead, we'll arrange things into rows below the current letters.

OUTPSNIVERFM
ABCDGHJKLQWX
YZ

Now we read off the letters in columns and get: "OAYUBZTCPDSGNHIJVKELRQFWMX"

This is what we use as the encryption/decryption key. (Sorta, more later)

Note: The reason we formed the rectangle and read off by columns was to prevent a large number of letters in the key being in the same place they are in the alphabet. Every letter after the "greatest" (last) letter in the key phrase would be intself. The reason this is important should become apparent in the next part.



2) The encryption method. (This is somewhat useful to know).

It is a simple Monoalphabetic single substitution cipher. In other words, each letter of the original text corresponds to eactly one letter of the ciphertext, and the substitution made is always the same. So if A encrypts to B, then all As in the plaintext will become Bs in the ciphertext. But I figure most people probably guessed that when trying it out.

So, continuing the example above, we make a substitution table as follows.
ABCDEFGHIJKLMNOPQRSTUVWXYZ
OAYUBZTCPDSGNHIJVKELRQFWMX

The algorithm works by simply looking for the current character in the table and replacing it with the character below (or above for the reverse operation).

Note: I used the same code for both encryption and decryption since it was easier to just invert the key to get the reverse effect. (So my algorithm always looked up the letter in the top row, and replaced it with the letter in the bottom row. Also, that was what I chose for decryption, so if people are writing their own decrypters they don't have to worry about inverting the key or the algorithm. The inverse key was used for the encryption.)

Anyways, I guess I should leave a quick example of inverting the key, even though you don't need to do this when decrypting. All you have to do is sort the second row into alphabetical order while maintaining the relationship with the row above.

BEHJSWLNOPRTYMAIVUKGDQXZCF
ABCDEFGHIJKLMNOPQRSTUVWXYZ

Of course, since the code always replaces the top letter with the bottom letter, let's just swap these two rows now.

ABCDEFGHIJKLMNOPQRSTUVWXYZ
BEHJSWLNOPRTYMAIVUKGDQXZCF

And there we have the inverse key. If we run the algorithm on some plaintext, and the on the resulting cipher text using these two keys (in any order) we get the plaintext back.




3) Example!

Lets use the key above to excrypt "WELCOME TO THE OPU"

We'll use the inverse key for encryption.
ABCDEFGHIJKLMNOPQRSTUVWXYZ
BEHJSWLNOPRTYMAIVUKGDQXZCF

The ciphertext is then: "XSTHAYS GA GNS AID"

Now, if we try to decrypt that using the original key.
ABCDEFGHIJKLMNOPQRSTUVWXYZ
OAYUBZTCPDSGNHIJVKELRQFWMX

We get back the original plaintext: "WELCOME TO THE OPU".



Hope that helps.

Btw, it probably doesn't help to guess the key word or key phrase. You don't really need it. Instead, you should try to work out the substitution table involved. Although, if you solve one, it might be fun to figure out the keyword/keyphrase based on your substitution table. =)

Have fun
(And I really need a monospaced font. Why do people use anything but?)
 

[Eddy-B]

to add to this:
ABCDEFGHIJKLMNOPQRSTUVWXYZ
ITDOESNTMATTERWHATUPUTHERE

...as long you use all 26 letters scrambled around. There's no special need to use a phrase like hooman suggested, You can replace ANY of the 26 letters with ANYTHING else (as long you don't use the same letter twice in your encryption "code").
This is a common puzzle-game i've solved many times (in those puzzle-books). They give you a crossword, but filled out with numbers 1~26 in all the squares, where each number always represents the same letter throughout the puzzle. To help you out, they might give you 1 small (4 or 5 letter) word to start with.

Not much of an encryption, but easy to decypher by just using common sence. If you really want encrypted text, that could be decrypted of course, you'd use something else. For instance this same method hooman gave, but then after you've "encoded" your message, add 1 to the first letter, 2 to the second letter, 3 to the third etc etc.. (oh, and Z+1=A). Now that makes it more difficult to decrypt, if not impossible. You can use all kinds of encryption methods, as long they are mathematiclly reverseable.  (in case you come up with an encryption that is unreversable, contact a patent's office )

Have fun!

[Hooman]

Yes, I seperated out the keyword/keyphrase from the key for a reason. You can use any permutation of the alphabet for a key, but it's harder to remember and I don't really want to have to chose one myself. That's why I went with the key generation technique using a keyword/keyphrase. But again, this also plays into how I said that part isn't really important and all you need is the substitution table to break it. (Which is really the only thing the encryption algorithm works with).

(in case you come up with an encryption that is unreversable, contact a patent's office )

Wouldn't that make it useless?  
Or are you talking about a random number generator here?  :lol:

... Now that makes it more difficult to decrypt, if not impossible.

Try it out and I'll break it. In fact, I know methods specifically designed to break such a scheme. It really doesn't buy you as much as you'd think. (A page or more of text usually gives sufficient information).

 

[BlackBox]

As far as encryption that uses mathematical methods.

There are symmetric ciphers and asymmetric ciphers. Symmetric just means you use the same key or group of keys to decrypt or encrypt data, also known as secret key cryptography. I won't get into asymmetric ciphers, an example of such is public key cryptographic systems that are in use all over the internet.

Also, there are block based and stream based ciphers.
Block based ciphers only operate on set amounts of data at a time. One such example is a simple substitution like Hooman and Eddy have discussed above. (It operates on one character at a time in that case). The method of transforming data generally doesn't change in a block based cipher.

Stream based ciphers operate on a continuous flow of data, generally changing the transformation system used as the data is encrypted.
One very famous example is the Enigma typewriter the Nazis used during WWII. It used a series of rotors that substituted letters, but would change their mappings after each letter.
For example, say initially A => X in the Enigma system. After a letter "A" was entered it would print an X, then the rotors would move and the transformation would be altered. Now A => N, and so on.
The Enigma system used the rotors to map the letters together. (for example, rotor 1 has all the original letters. then electrical contacts mapped each letter to different letters on the 2nd rotor. After each character however the rotors would move and the mappings would change).

However the Enigma system is really weak by todays standards. For one to decode a message, all you'd need to know is the initial settings of the rotors and the electrical mappings between.

Other stuff you may want to know:

Exchanging keys between computers thru an insecure line. (Real life example, SSL). Most use a system known as Diffie-Hellman key exchange. I don't know very much about this though so you'll have to google it to find out more.

Another good site to check would be www.rsasecurity.com. They've written a lot of industry standard algorithms that are out there. RC4 is one example.

[Eddy-B]

(in case you come up with an encryption that is unreversable, contact a patent's office )

Wouldn't that make it useless?  
Or are you talking about a random number generator here?  :lol:
 

no .. and no!

one-way encryption is commonly used for encrypting passwords. Eaxmples are DES, 3DES (and also MD5 if im not mistaken).

They are impossible to decrypt, other then using trial-and-error methods. And if there's millions of keyphrases that could have been used, makes that solution unworkable.

One-way encryption is only useful for things like password checking, since you cannot decrypt a message, but only check to see if your message is what you expect it to be or not. But if you want a nice encryption to try your skills at, i'll create one

[Hooman]

... of course block ciphers can be turned into stream ciphers using things like cipher block chaining, plaintext chaining, etc. (The usual use of a block cipher being used in it's original form is often referred to as electronic codebook form, and is generally fairly insecure).


So... Diffie-Hellman Key Exchange:

The two parties A and B select a public prime p. The whole world can know this number for all they care, but it should be fairly large and there are certain desirable properties when selecting it. (Such as whether or not p-1 has any small factors). They also select a primitive root a (mod p). This is also public. There are a number of ways primitive roots are described, but I guess the most relevant is that it's powers form all the numbers from 1 to p-1 when taken modulo p. In other words, any number in the range 1 to p-1 defines another number in that same range, 1 to p-1, that is unique. So basically raising this number to a power is mathematically reversible, as there is only one correct answer to reverse it (and exactly one correct answer).

Now, A chooses a secret random number x with 1 <= x <= p-2, and B selects a random number y with 1 <= y <=p-2.

Now, A computer a^x (mod p) (Where ^ denotes raising to the power of) and sends this number to B. B similarly computes a^y (mod p) and send this value to A.

Now A calculates K = (a^y)^x (mod p). (Not that A does not know y, but does know a^y).
B calculates K = (a^x)^y (mod p).

It turns out that these values for K are indeed the same value. (The secret key). Not that A never learns B's secret y, and B never learns A's secret x. But they do end up with a common key K. Also, keep in mind that for A to calculate the secret key K, it had to know it's secret random number x, which is never sent over the net and can't be intercepted. Also, B had to know it's secret random number y, which was also never sent over the net and can't be intercepted.

It you were to determine with x or y then you could easily break the system, but you only have values a^x (mod p) and a^y (mod p). The interesting thing is that these values uniquely determine x and y, so if you find a solution you know you've cracked it. However, there isn't really any good ways of calculating x or y given all the public information. Also, if the key size is large, say 1024 bits, then there are 2^1024 possible bit combinations to try if you wanted to brute force this. If you could test over 1 billion values per second (about 2^30), you'd still need about 2^(1024-30) = 2^994 seconds. And since there are about 2^25 seconds in a year, that's still about 2^969 years. Certainly not something you can expect them to solve in a reasonable amount of time. Not is it at all likely they'll get lucky and guess the rigth value. But if they did, they would know they were right.


So yeah, the security here relies on the difficulty of the discrete logarithm problem. (Finding the exponents given the base, the modulus, and the result of the exponentiation). On the plus side, actually performing the exponentiation is really easy and fairly fast for a computer to do.




Edit:

no .. and no!

one-way encryption is commonly used for encrypting passwords. Eaxmples are DES, 3DES (and also MD5 if im not mistaken).

Technically that's hashing, and not encryption. Encryption is inheriently reversible. Although, a number of encryption algorithms have proven useful in making one-way hash functions. The difference is usually that a lot of information is thrown away so there is no mathematical way to obtain one correct solution to a reverse problem because there is none. There are usually many solutions. Which is why I'll probably never learn what that 4th cheat was for OP2. I've found collisions (the so called false solutions), but there is really no mathematical way to tell the false solutions apart from the real solutions. Of course, you can use certain intuition yourself, like the collisions I found were grammatically incorrect to the point that there was no way they could have been right, but then, how close is close enough? If you find any collision, that's enough to fool the computer, and you don't actually need to know the real password/cheat.

[Eddy-B]

okay - quick one:

TAFBRNJSIJP EKYH'R OCURCIC, ILG NVV CRIXMDCSFZ. MBSHWNMCPJ FA HNZBUMETAIO BKEMFRYGSS. FVPVSAGZ, N QFRVGZ DY KZQFULKANH GWDSQIUAPG DRZH EBFEMB QSQGUU DJ JJJIOI XRE-CSN HVNK BPCTKANHX. PVX GIPQCVETKH RM MOOZPQW LRFO H XSS UP KQSZXTTCSFZ VQ IOIMPH GSID BU UACVE OJ VD WWFLNBBKAWFV SID SU VRWPNT BVI NFDENSJ TMTVOERL SU M TCWEXJH EBFBNNB FQVEVXV QWYRA KF RZTG. BHJCL YFO RTTEUVB JJMF DWDFYOBVL. GJUQM XS NQY C'VW SPTPMRDJ SFZHA KKXEB LOCL MSGP 4QW CYANW AQI VCA EG2. U'FN DKSFA XPWXGBIVPF (XDF JC MVLMMV DBRUS WPWYRHUOE), SFY ZFHAJ TO ENAQRX GO HHQWYMMVLHQG DTO DF FMOP JPR HFVYW ATACVLYSI SDUBE AEIB JPR KTGW ZSZBUKXRH. AV LDLCOM, TJR UDG VXV AXQTMKQ MSZIQCSFZ SIQHTRTI, VEHX SYA FXEFOJQDXN U BIQDY OSLU COJLMMVLHQGHN RXOGEFOTK LN NTV SSHNU VBPY ZFHAJ HXP BJ MCX MSUB ASAAI AOWE VGHW BTSLH, ERK LRTI, URU CAVEC MH JHCLJ KZHPVO? ZG YOW KFLG LOH GYFGPKREY, FLZI'S QFNVBU QS NUVC WCE JBUELELE, ZCX WMU BPJ'Q JCTCNDEK TGHQ DF WAIL JPR KTGW SJBCXWUL/IEGTC.


try to decode that

[BlackBox]

Okay Hooman, this is probably a ridiculous question but I'll ask it anyway.

If the two computers A and B send the values [doHTML]a^x and a^y[/doHTML], respectively, you say the numbers x and y are secret to the computer that generated them. However it would seem both machines know the value of a.

But couldn't machine B do something like [doHTML]log_a (a^x) = x[/doHTML] (filling in the known values, a and [doHTML]a^x[/doHTML] of course, using a change of base common, base 10, log [doHTML]a^x[/doHTML] over log a ) and there you have it, figures out the value of x. Same thing with machine A figuring out Y.

Or am I misreading something?

[Hooman]

Yes! You are misreading something.  

These logarithms are dealing with the integers modulo p, not with the real numbers. Your answers must all be integers to make sense. Try to think about what a fractional log answer would mean. Not really a whole lot actually. Also, keep in mind that logaritms on real numbers produce a nice continuous graph, and the algorithm used to calculate the log of a real number uses that continuous property. Getting an answer also isn't a straigh calculation. Instead, the algorithm allows you to produce a convergent sequence of successive approimations that allows you to calculate the desired value to any degree of accuracy, but in most cases will never be completely accurate. (A computer can't represent an irrational number in the usual form, only symbolically. Finite memory means finite precision.)

Now when working with the integers you don't get this concept of continuity. Also, the numbers jump around a lot more. Largely due to the modulo part causing wrap-around.

Consider the integers modulo 7. Now 3 is a primitive root of module 7.

[doHTML]3¹[/doHTML] = 3
[doHTML]3²[/doHTML] = 2
[doHTML]3³[/doHTML] = 6
[doHTML]3⁴[/doHTML] = 4
[doHTML]3⁵[/doHTML] = 5
[doHTML]3⁶[/doHTML] = 1

Note that all arithmetic was done modulo 7. Also note that all the values from 1 to 6 were generated in some order. (Because 3 is a primitive root of 7).

Do you see much of a pattern here? This reordering tends to appear somewhat random, which is why it's often used. Also, this is essentially just a way of reordering the numbers from 1 to 6. (The powers 1 to 6, generate answers 1 to 6, in some order). Each value appears exactly once as an answer. So, at least in theory, you could write out a table of pairings that would allow you to move from one representation of some data to the other. It is mathematically reversible.

Also, since it's easy to perform the exponentiation modulo some number, it's easy to check if a particular solution is correct, and since there is exactly one right answer, you'd know for sure. On the other hand, it's not easy to find the exponent given the other values. (Finding it is known as the discrete log problem). One sure way of finding an answer is simple brute force. Try all exponents until the exponentiation gives the answer you're looking for. Unfortunatly, for very large primes, there are a very large number of exponents to try, and trying them all could take till the end of the universe.

[Hooman]

Btw, Eddy. You enciphered:

"Technically that's hashing, and not encryption. Encryption is inheriently reversible. Although, a number of encryption algorithms have proven useful in making one-way hash functions. The difference is usually that a lot of information is thrown away so there is no mathematical way to obtain one correct solution to a reverse problem because there is none. There are usually many solutions. Which is why I'll probably never learn what that 4th cheat was for OP2. I've found collisions (the so called false solutions), but there is really no mathematical way to tell the false solutions apart from the real solutions. Of course, you can use certain intuition yourself, like the collisions I found were grammatically incorrect to the point that there was no way they could have been right, but then, how close is close enough? If you find any collision, that's enough to fool the computer, and you don't actually need to know the real password/cheat."


And the cipher was NOT Mono Alphabet Single Substitution. It doesn't appear to be Poly Alphabetic Single Substitution either. (Which is kinda what I expected from your description of your idea).
 

[zanco]

Wow!
Thx guys.

[Hooman]

Hmm, I figured I'd revisit Eddy's little cryptogram here since I made a few mistakes in my initial analysis. Probably my biggest was I analysed all of the text given, even though only the letters were enciphered. (The spacing and punctuation threw my analysis off). So, I went and stripped that stuff out and tried again, just to see if I'd get better results.


Anyways, first lets see how it was probably done.

It seems a Mono Alphabetic Single Substitution Cipher was applied to the plaintext with the following (partial) key: "lusc ygdi kamnfb rvtopw he". Note that I have left spaces in it where certain letters could not be determined. The reason for that is simply that they weren't ever used, so there is no information on them. Than and you can assign them to be anything and it'll work.

After that, the letters were cyclically shifted based on their position (ignoring spacing and punctuation). I used the following code to undo it, and then the result is subject to the same analysis as any plain old mono alphabetic single substitution cipher. (I really need an abbreviation for that, don't I?)

Code: [Select]

    Dim i As Long
    Dim shift As Long
    Dim asciiCode As Long
    
    For i = 1 To Len(strText)
        asciiCode = Asc(Mid$(strText, i, 1))
        If asciiCode >= 65 And asciiCode <= 90 Then
            asciiCode = (asciiCode - 65 - shift) Mod 26
            shift = shift + 1
            If asciiCode < 0 Then asciiCode = asciiCode + 26
            Mid$(strText, i, 1) = Chr$(asciiCode + 65)
        End If
    Next i

Note that the shift is only updated for alphabetic characters.


So in all, the result is a Poly Alphabetic Single Substitution Cipher, with 26 alphabets. (Just cyclical shifts of the same one).

Anyways, when I tried to resolve the number of alphabets again (assuming poly alphabetic encipherment), I found a fairly large spike in probability at 26 alphabets. It still only suggested that about 30% of the alphabets represented mono alphabetically enciphered text, so I may have missed this. But then, the next highest was about 7%, and I was kinda expecting 26 to begin with from Eddy's early description. But of course, I'd already figured it out by the time I ran this test properly, so I guess none of this really matters.

Btw, the test was just a simple statistics measure of the amount of variation in the characters used. In random text, you'd expect abotu equal usage of all letters, but in English text, you'd expect some characters to appear much more frequently than others, like the letter "e".


So, now that I've stopped being dumb about analysing the whole thing like it was encrypted, maybe I'll actually get somewhere on Eddy's new challenge.