Can I encrypt a message by swapping bits in the text?

Question

I have tried out an encryption method, in which I swap bits in the text.

The text length is N bit, then I generate several random number pairs in the range 0..N-1, as [n,k] pairs. After that, I swap the n-th and k-th bits in the message, if they are different, of course. After several swaps the message becomes unreadable.

The message can be decrypted by applying the swaps in the reverse order.

Can this be a good encryption method or is it equivalent to the usual XOR cipher, or even weaker?

For example, I can generate the random number pairs with a pseudo-random number generator, with a starting seed. And the seed can be obtained from a passphrase, for example, an integer hash of the passphrase. Then I can use the passphrase to encrypt the message this way, and the same passphrase for decrypting, as the random number pairs will be the same again, due to the same seed applied at the start.

Answer 1

First problem is you're not specifying at all how many swaps you need to do for a given message length, other than saying it's "several." For an $n$-bit messsage there are $n!$ ways of rearranging its bits, gives a lower bound of $\mathrm{log}_2(n!) = \sum_{i=1}^{n}\mathrm{log}_2(i)$ bits for on how much pseudorandomness you'll need. Rather than analyze a precise number of rounds your random swaps method needs to achieve a good result, however, it's just simpler to substitute in a Fisher-Yates shuffle that'll fairly permute an $n$-item sequence in $n$ steps.

But whatever you do, even if we assume true random bit permutations, the technical answer is that this is straightforwardly insecure because an adversary can easily and reliably distinguish encryptions from random strings by looking whether the number of ones vs. zeroes is the same as their chosen plaintexts. A special case of this is that any message that's only zeroes or only ones encrypts to itself.

Even if we assume the attacker doesn't get to choose plaintexts, they can use this property to test whether a given ciphertext could be the encryption of some plaintext they guess at. Take for example the binary ASCII codes for these strings:

HAHA ===> 01001000 01000001 01001000 01000001 ===>  8 ones
YEAH ===> 01011001 01000101 01000001 01001000 ===> 11 ones
NOPE ===> 01001110 01001111 01010000 01000101 ===> 14 ones

If I see a ciphertext with 11 ones I can tell that it's definitely neither HAHA nor NOPE, but could still be YEAH.

Answer 2

If an attacker has a way of getting you to encrypt a message of their choosing this way, it would be trivial break. Imagine you swap each bit randomly with another bit. If you have a message of 800 bits an attacker could discover the entire pattern with 11 attempts. The attacker could set bits 0-399 to 1 and map those to 1s in the encrypted message and the 0s to the 0s. Then you could send bits 0-199 and 400-599 to 1 and try again. The ones that were 0 in the first attempt and 1 in the second attempt would map to 400-599, the ones that were 0 in both would be 600-799, the ones that were 1 in both would map to 0-199, and the ones that were 1 then 0 would map to 200-399. So first you can map two groups of 400, then you can whittle it down to 4 groups of 200 in another message. Keep seeing half of each known mapping to 1 and you get to 8 groups of 100, 16 groups of 50, 32 groups of 25, 64 groups of 12/13, 128 groups of 6/7, 256 groups of 3/4, 512 groups of 1/2, and finally to a 1:1 mapping for all 800 bits in 11 messages.

Depending on how you generate the pairs, that might be enough for other message lengths. For instance say you use a seeded random number for each bit except the last to determine what position to map the cell too. The number is generated as 0.0 to 0.999999999 and multiplied by 800 to choose which bit to swap with (including the first bit which means no swap). If it turns out to be bit 399 then the number is around 0.49. That means a message of length 800 would swap bit 0 to 399, a message of length 400 would swap to bit 199, etc. Submitting just a few messages should be enough to figure out the algorithm and find the key.

As Land mentioned if you don't actually modify the data and just swap the bits, information can be gleaned about the message by the number of 1s and 0s. Say what you are encrypting is a 1024 bit private key. Let's say it has 500 1s and 524 0s. You've now greatly reduced the amount of time needed to brute force the key because you can skip checking any key that has a different number of 1s and 0s.

Answer 3

You can do that. But this is a bad encryption algorithm. It can't be used in real application, because one can easily recover the plaintext from its ciphertext.

Answer 4

Can you? Sure! It'll be a great exercise to code up and then you can research why it might be particularly weak to attacks (such as what has been mentioned here).

In fact I'd really encourage you to explore cryptography as it is both fun and frustrating at the same time.

When you've decided you've had enough, I'd then recommend some deep diving on the web for proper cryptographic implementations, the pitfalls of crypto in software, and what not. I won't mention resources as what I knew is far out of date.

But yes, learn- yes- you can- yes- do it!

...then learn to do it the 'safe' way. Because crypto is hard. I can't tell you the number of stories you see/hear/read about people that thought crypto was easy, used their own method, and got p0wn3d.

Answer 5

This sounds like a kind of fractionated transposition cipher. My understanding is that some kinds of transposition-alone ciphers can be more difficult to crack than double-Playfair (WGBH 2000), and fractionated transposition ciphers, such as ADFGVX Cipher are considered more difficult to crack than transposition-alone ciphers (Rijmenants).

As others have pointed out, it is trivially easy, if you encode the letters using ASCII, to rule out some possible messages -- messages that have a different Hamming weight than the (transposed) ciphertext.

However, it is in principle for transposition alone (with other kinds of encoding) to give (with sufficiently unguessable shuffling) "perfect security", although this doesn't seem useful in practice. (Because other, apparently simpler techniques also give "perfect security"; and because we find in practice that we're willing to give up perfect security in order to make key distribution easier).

For example: algorithm A:

• Ahead of time, Alice and Bob share one-time pads of random numbers.
• Alice encodes a message into a series of 40 character lines using some constant-weight code (every possible message in that encoding has exactly the same Hamming weight).
• Alice rearranges the bits in each encoded line with a Fisher-Yates shuffle to fairly permute all the bits in the 40-character line (thank you, Luis Casillas), using the numbers from her one-time transmit pad to decide which of all possible shuffles to use.
• Alice sends a series of lines to Bob, and destroys the used pages of her one-time transmit pad.
• Bob unshuffles the bits in each line of text using his one-time receive pad, then decodes each line into 40 characters of plaintext, and destroyed the used pages of his one-time receive pad.

From any possible ciphertext generated by this algorithm A, a cryptanalyst can "decrypt" any possible message with the same number of lines of text, simply by using a different one-time pad, so algorithm A has perfect security. (A particular ciphertext might represent "YEAH", "NOPE", "HAHA", "GOGO", etc.) (Alas, this uses up the one-time pads of numbers much faster than enciphering the same messages with traditional XOR encryption one-time pad, which also has "perfect security").

My understanding is that a fixed, publicly-known transposition could be used in the inner block of a Even-Mansour cipher.

Another kind of encoding that seems better than ASCII for transposition ciphers is: encoding text into a complete deck of cards, as suggested by Tim Warriner and Lee J Haywood.

Answer 6

There are all sorts of simple encryptions that are nearly impossible to crack, without having a large enough sampling, or without having a test program to brute-force some detectable patterns.

However, for a personal message system, this method seems adequate for intermediate use.

It would not last as a mass-applied method, due to the simplicity of the structure.

Most current encryptions use "more symbols", to represent "less symbols", which is what makes them harder to decipher. At the end of the day, a simple 1:1 bit-swap or/and bit-shift is as easy to figure out as a "G=U" decoder ring. Even when you are flip-flopping bits, "pseudo randomly", as you state.

You must also know that pseudo-random number formulas are not universal across computer systems or even computer languages. (They would have to have the exact same system and program as you, unless you make your own random number generator too.)

You may think a pseudo random number generator looks random, but none are. They are all repeating cycles of cycles of cycles. Plot the results in a linear graph, and you will easily see the frequencies that repeat. The results are always "similar", but not exactly the same. Looking at each individual result, it is hard to see.

Honestly though... Encryption is the same. They just use larger "prime numbers" for the cycle factor. So the frequencies are almost unplottable, for human observation.

But that is still the biggest flaw... They are a loop. So there will always be a collision at the point which the numbers roll-over. After one digit past the prime number, where the result becomes a factor of that prime number now. That is the point where it doesn't matter what your original key is, because there are infinite collisions worth of keys that also decipher the encryption.

Which rolls back to your "key" to decipher yours... Yes, your single key may look fancy... But, at what point does your cycle repeat, and another key will result in the same decrypted output. Find that, and you find your first answer to how good it may potentially be.

Eg, if it's less than 400 trillion, trillion... It can be deciphered in about a week, by any simple brute force super-computer program. (With access to your code that encrypts and deciphers, as a reference.)

When a dictionary scan yields multiple words, or all words, it has essentially been cracked.

"BOB" encrypted with a larger "symbols", (1024 bits) may look like this... "6&#+#54@&2dyah##6&278#5dtaivGfe:-#7765#++$+"

Hard to tell that it equals "BOB", and now you see another flaw of encryption... Bloating.

Now you know why a secure page takes longer to load. It's nearly 20x the size as an unencrypted web page, with 512 bit encryption.

Answer 7

Just adding... Websites and many high security programs use a three-key setup.

You have key A.

Some third party has key B.

A recipient has key C.

You encode a message with your key "A". That message gets sent to the third party, who applies his key "B". They send it to the recipient who deciphers it with the "C" key.

The person with the "B" key is essentially recoding it, so it deciphers with the "C" key. They can not read it, and when a message is sent in reverse, it does the same thing. Applying "B", to the "C", message, makes it decipherable only to the person holding the "A" key.

That is what makes a SSL (secure website), secured. A hacker could not fake a secure site, without knowing the "B" key, needed for making your message readable by the site on the other side. Same for the site... Since your request is not decipherable without the site key. (In theory)

Perhaps if you had that "undocumented formula", managed by a third party... Your encryption method at both other ends, would have some greater potential. (No real ability to obtain the source code, or decompile it.)