XOR encryption (XOR) principle and implementation (**)

Table of contents

Introduction to XOR encryption

XOR encryption algorithm (including a simple C language encryption and decryption source code)

XOR Encryption (XOR) Principle and Implementation

===========================================

XOR encryption (XOR) principle and implementation

  • 2019-01-12
  • program development

Implemented an online encryption and decryption tool with js, supports Chinese as the key, welcome to try it

https://www.boydwang.com/xor.html

What is XOR encryption

XOR encryption is an encryption algorithm that uses XOR calculation in the computer. The principle of XOR calculation (symbol marked as ‘^’) is that the same is 0, and the difference is 1

0 ^ 0 = 0
1^1 = 0
1^0 = 1
0 ^ 1 = 1

Since the result of 1 ^ 0 or 0 ^ 1 is 1, cannot directly deduce whether the original plaintext is 0 or 1 from the result 1, so as to achieve the purpose of protecting the plaintext.

XOR encryption feature

XOR encryption has the following properties (quoted from Wikipedia):

Simple XOR cipher (English: simple XOR cipher) is a simple encryption algorithm in cryptography, which operates according to the following principles:
1. A ^ 0 = A
2. A ^ A = 0
3. (A ^ B) ^ C = A ^ (B ^ C)
4. (B ^ A) ^ A = B ^ 0 = B // plaintext B; password A

From principle 4, it can be obtained that for the same plaintext B, using the key A to perform two XOR operations on it, the plaintext B can be obtained. We just use this feature to implement encryption and decryption

XOR encryption algorithm

The XOR encryption algorithm consists of three parts, which are

  1. clear text
  2. key
  3. XOR operation rule

The process is to traverse each character of the plaintext, and take out one or more characters from the key according to the XOR operation rules, perform XOR operation with the characters of the plaintext, and synthesize the XOR result into a new string.

However, due to the characteristics of XOR operation, it is possible that after XOR operation, it becomes an invisible character, and it may not be possible to transmit ciphertext through strings, so base64 encoding is introduced here, because base64 encoded strings are Visible characters,

For more information about base64 encoding, see Js Base64 Encoding

So the encryption algorithm becomes:

  1. The plaintext and the key are XORed according to the XOR operation rules to generate the key
  2. Base64 encode the obtained ciphertext, and finally return

The decryption algorithm accordingly becomes:

  1. Base64 decode the ciphertext to get the original ciphertext
  2. XOR the ciphertext with the ciphertext according to the same XOR operation rule to get the plaintext

XOR algorithm

The XOR operation algorithm is to solve the problem of how to perform XOR operations between plaintext and ciphertext, because the lengths of plaintext and ciphertext may be different, how to ensure that each character in the plaintext has a corresponding ciphertext character for XOR, and When decrypting, it is guaranteed to perform the XOR operation according to the same algorithm to obtain the plaintext, which is considered by the XOR algorithm. Here we will use a new operation called the remainder. The case of negative numbers is not considered here.

The remainder operation (usually recorded as %) means the remainder after dividing the dividend by the divisor, such as 8 / 5 = 1 remainder 3, so 8 % 5 = 3, and the remainder operation stipulates that if the dividend is smaller than the divisor, then take the remainder The result is the dividend, so 5 % 8 = 5, see the following example:

0%3=0
1%3=1
2%3=2
3%3=0
4%3=1
5%3=2
6%3=0
7%3=1

Did you find out that the result is always a cycle of 0, 1, 2, we can use the index of each character in the plaintext to take the remainder of the total length of the ciphertext, and use the result as the index subscript of the ciphertext to take out the corresponding The ciphertext characters can be XORed with the plaintext characters.

Look at the example below

Power shell implementation

The encryption key can be changed by changing the value of the variable key

$Script:key = "3567d8cndkei%*x9(-32[]KDF(32222"

function Decode($cyphertext) {
    $keyArray =[System.Text.Encoding]::ASCII.GetBytes($key)
    $encodedArray= [System.Text.Encoding]::ASCII.GetBytes([System.Text.Encoding]::ASCII.GetString([System.Convert]::FromBase64String($cyphertext)))
    $plainText = ""
    $keyposition = 0
    $encodedArray | foreach-object-process {
        $plainText += [char]($_ -bxor $KeyArray[$keyposition % $KeyArray.Length])
        $keyposition += 1
    }

    return $plainText
}

function Encode($plainText)
{
    $KeyArray= [System.Text.Encoding]::ASCII.GetBytes($key)
    $cyphertext = [System. Byte[]]::new($plainText. Length);
    $keyposition = 0
    $plainText.ToCharArray() | foreach-object-process {
        $cyphertext[$keyposition] = $_ -bxor $KeyArray[$keyposition % $KeyArray. Length]
        $keyposition += 1
    }

    return [Convert]::ToBase64String($cyphertext)
}

Test

Decode(Encode("324328***)x-sdfsaf2344")) | out-string

Results

Same result as unencrypted data

image

异或加密(XOR)原理及实现

===========================================

Introduction to XOR encryption

Author: Ruan Yifeng

Date: May 31, 2017

This article introduces a simple, efficient, and very secure encryption method: XOR encryption.

1. XOR operation

Among logical operations, in addition to AND and OR, there is also an XOR operation, which is called “exclusive or operation” in Chinese.

Its definition is: when the two values are the same, return false, otherwise return true. That is, XOR can be used to determine whether two values are different.

true XOR true // false
false XOR false // false
true XOR false // true
true XOR false // true

The binary operation of the JavaScript language has a special XOR operator, written ^.
1 ^ 1 // 0
0 ^ 0 // 0
1 ^ 0 // 1
0 ^ 1 // 1

In the above code, if the two binary bits are the same, it returns 0, which means false; otherwise, it returns 1, which means true.

2. Application of XOR

The XOR operation has a wonderful feature: if you perform XOR on a value twice in a row, the value itself will be returned.

// first XOR
1010^1111 // 0101

// second XOR
0101^1111 // 1010

In the above code, the original value is 1010, and then choose a value arbitrarily (1111 in the above example), do XOR twice, and always get the original value 1010 in the end. This is easy to prove mathematically.

3. Encryption application

This characteristic of XOR makes it suitable for encryption of information.

message XOR key // cipherText
cipherText XOR key // message

In the above code, the original information is message, the key is key, and the encrypted text cipherText will be obtained by XOR for the first time. After the other party gets it, use the key to do an XOR operation again, and the message will be restored.

4. Perfect secrecy

During World War II, countries conducted a lot of research and practice on cryptography for telegraph encryption, including XOR encryption.

After the war, American mathematician Claude Shannon published his research results publicly, proving that as long as two conditions are met, XOR encryption cannot be cracked.

The length of the key is greater than or equal to the message // That is, the same encrypted ciphertext will not repeat segments. Unless it is deliberate, is a key that is too long practical? So repetition is inevitable?

The key must be one-time, and it must be randomly generated each time //That is, there will be no repetition between multiple encrypted different ciphertexts

The reason is simple. If the key is random each time, the generated CipherText has all possible values and is evenly distributed, and it is impossible to see any characteristics of the message from the CipherText. In other words, it has the greatest “information entropy”, so it is completely impossible to crack. This is known as the “perfect secrecy” of XOR.

A key that satisfies the above two conditions is called one-time pad (abbreviated as OTP), which means “one-time pad”, because such keys used to be printed as password pads, Every time you use it, you must pick a key from it.

5. Example: hash encryption

The following example uses XOR to encrypt the user’s login password. See the actual running effect here.

The first step is to calculate the hash of the password when the user sets the login password. The MD5 algorithm is used here, and other hash algorithms can also be used.

const message = md5(password);

The second step is to generate a random key.

// Generate a random integer in the range [min, max]
function getRandomInt(min, max) {
return Math. floor(Math. random() * (max – min + 1)) + min;
}

// Generate a random hexadecimal value between 0 and f
function getHex() {
let n = 0;
for (let i = 4; i > 0; i–) {
n = (getRandomInt(0, 1) << (i - 1)) + n;
}
return n.toString(16);
}

// generate a 32-bit hexadecimal value to use as a one-time key
function getOTP() {
const arr = [];
for (let i = 0; i < 32; i ++ ) {
arr.push(getHex());
}
return arr. join(”);
}

In the above code, the generated key is a 32-bit hexadecimal value, which corresponds to the 128-bit binary hash generated by MD5.

The third step is to perform XOR operation to obtain the encrypted message.

function getXOR(message, key) {
const arr = [];
for (let i = 0; i < 32; i ++ ) {
const m = parseInt(message. substr(i, 1), 16);
const k = parseInt(key. substr(i, 1), 16);
arr.push((m^k).toString(16));
}
return arr. join(”);
}

Using this method to save the user’s login password, even if the encrypted text is leaked, as long as the one-time key (key) is not leaked, the other party cannot crack it.

(over)

XOR encryption algorithm

XOR encryption is a very simple encryption algorithm, which is not difficult in terms of principle or operability, so it is widely used when doing some simple encryption.

But because it is very simple and easy to crack, do not use this method to encrypt more private information.

Let’s briefly introduce the XOR operation:

The mathematical operator is XOR (exclusive OR), which is usually represented by the symbol “^” in the computer (in English mode, hold down the shift key + the number 6 above the keyboard)

In binary:

1 XOR 0=1

0 XOR 1=1

1 XOR 1=0

0 XOR 0=0

It can be seen that if two numbers are the same, take 0, and if they are different, take 1.

example:

Operation 11001^01011=10010

When XOR operations are performed on numbers expressed in other bases, they should be converted into binary numbers before performing operations. (Insufficient bits are filled with 0 in front)

example:

Calculate 6^3=110^011=101

***************************************************** *****

XOR operation is reversible.

That is: if a^b=c, then b^c=a (a, b, c represent 0 or 1 respectively)

Using the previous XOR operation rules, we analyze one of them:

1 XOR 0=1 then 0 XOR 1=1

Principle: According to the operation rules of XOR, the same is 0, and the difference is 1;

If two numbers a and b are the same, a=b, then when any number is XORed with 0, the number itself is obtained, which is another number;

Apply the two operation rules of 1 XOR 0 = 1 , 0 XOR 0= 0 (equivalent to taking this number).

If the two numbers a and b are different, a=~b, then when any number is XORed with 1, the opposite of the number is obtained, that is, another number

Apply the two arithmetic rules 1 XOR 1 = 0 , 0 XOR 1 = 1 (equivalent to inverting the number).

***************************************************** ***********

We might as well promote the reversibility of XOR, XOR any two strings of binary numbers, and then XOR with any string of binary numbers to get another string of binary numbers.

That is, a^b=c, then b^c=a. (a, b, c respectively represent a string of binary numbers)

Formally the same as the above formula.

Then, if a is the information to be encrypted, there is a key b, XOR is performed on a and b, and the obtained c is the encrypted information, which can be transmitted.

After getting c, you only need to XOR with b again to get the original information a.

If applied to a string, each character on the string represents a string of binary numbers.

example:

#include
main()
{
char a[]=”Password”; //The password to be encrypted (plaintext password, the original string that needs to be encrypted)
char b[]=”encryption”; //Key (the password to be used for encryption, the password for encryption and decryption)
int i;

//encryption code
for(i=0;a[i];i + + )
a[i]=a[i]^b[i];
printf(“Your Password is encrypted: %s\
“, a);

/*Decrypt code*/
for(i=0;a[i];i + + )
a[i]=a[i]^b[i];
printf(“You Password: %s\
“, a);
}