1. Sequence code

Symmetric encryption is generally divided into block ciphers and stream ciphers. The biggest difference between the two is that in encryption, block ciphers encrypt a group (generally 64 bits), while sequence ciphers encrypt a bit or a character.

1.1 RC4 cipher

The RC4 password process is as follows:

  1. An initial array S[255]={0, 1, 2… , 255}

  2. Then a seed secret key T is initialized, and the value of the secret key K is bit-cycled to T until T is filled.

  3. The seed secret key T is used for initial replacement of S table, and the replacement S table is obtained.

    The code is as follows:

    S = []
T = []

def stream_init(main_key) :
    Initialization :parmas main_key: initializes tables S and T for subsequent encryption or decryption
    
    global S, T
    S = [i for i in range(256)]
    T = [main_key[i%len(main_key)] for i in range(256)]   # 256
    
    # Permutation of S table
    j = 0
    for i in range(256):
        j = (j + S[i] + ord(T[i])) % 256
        S[i], S[j] = S[j], S[i]


Copy the code

  4. The next step is to continuously obtain a different secret key from the S table (core: continuous REPLACEMENT of the S table), and then perform xOR operation with one of the plaintext, to get a ciphertext. Similarly, the obtained secret key performs xOR operation with one in the ciphertext to obtain one in the plaintext.

    def deal_txt(text) :
    """ 2. Process plaintext → ciphertext or ciphertext → plaintext :param text or ciphertext :return: plaintext encryption or ciphertext decryption """ "
    i, j = 0.0
    a_text = ' '     # Returns the processed string
    for each_t in list(text):     # Iterates over each character to be processed
        i = (i + 1) % 256
        j = (j + S[i]) % 256
        S[i], S[j] = S[j], S[i]  # Permutation of S table
        
        t = (S[i] + S[j]) % 256
        k1 = S[t]                # k1 is the one-digit secret key obtained by substitution
        
        a_text += chr((ord(each_t) ^ k1))     # Convert the plaintext and K1 xOR values unicode to STR letters and then concatenate them into a_text.
    
    return a_text
Copy the code

  5. Each bit of plaintext is xOR with the secret key to get one bit of ciphertext, which is then joined together to return the ciphertext.

    if __name__ == '__main__':
    plaintext = 'zhang'
    key = 'fwefew'
    print(F "proclaimed in writing:{plaintext}And the secret key:{key}")
    
    stream_init(key)
    cipher_txt = deal_txt('zhang')
    
    stream_init(key) 
    plaintext2 = deal_txt(cipher_txt)
    
    print(F "cipher:{cipher_txt}, the plaintext after decryption:{plaintext2}")

# plaintext: Zhang, secret key :fwefew
(6) # ciphers: a ™, the plaintext :zhang
Copy the code

The encrypted result is compared with the official RC4 encryption result, and it is found that there is no fault. Note here: the official RC4 returns results in hexadecimal, while mine returns results in characters, which are essentially the same.

Fermat’s Little Theorem

Theorem: if p is a prime and a is not a multiple of P, then ap−1≡1(modp)a^{p-1}\equiv1(mod p)ap−1≡1(modp)

Proving Fermat’s Small Theorem:

There are many ways to prove it, of which the method using the congruence property is the least.

First take a prime number P and let x less than P,x⊆[0,p−1]x,x\subseteq[0,p-1] x,x⊆[0,p−1], The GCD (x, p) = 1, x = xmodpgcd (x, p) = 1, x = x mod PGCD (x, p) = 1, x = xmodp

Set the set X = {1, 2, 3,…, p – 1} X = \ {1, 2, 3, \ \ cdots,} {p – 1 \} X = 1} {1, 2, 3,…, p –

Set set Y = {(a (1) modp, (a * 2) modp, (a * 3) modp,…, a * (p – 1) modp} Y = \ {mod p (a \ times1), (a \ times2) mod p, (a \ times3) mod p \ cdots, a \ times (} {p – 1) mod p \} Y = {modp (a (1), (a * 2) modp, (a * 3) modp,…, a * (p – 1) modp}

We need to prove that the elements of Y are not zero and not equal, and we’ll see why.

  1. A is not a multiple of P; amodp≠0a modp \neq 0amodp=0;


    ( a x ( p – 1 ) ) m o d p = ( a m o d p ) x ( p – 1 ) m o d p ) indicates 0 (a\times(p-1))mod p = (a mod p) \times (p-1)mod p)\neq0

    It follows that none of the elements of Y are 0.

  2. By contradiction, all the elements of Y are different, and let x, Y ⊂Xx, Y \subset Xx, Y ⊂ x, assume ax(modp)≡ay(modp)ax (modp) \ Equiv ay(modp) Ax (modp)≡ay(modp), Ax ≡ay(modp)ax \equiv ay(modp)ax ≡ay(modp), this step is to simplify both sides by congruance.

    According to the division property in the modulus theorem, if GCD (a,p)=1gcd(a, p)=1gcd(a,p)=1, then x≡y(modp)x\equiv y(modp)x ≡y(modp), then x=yx=yx=y.

    X ≡y(modp) X \equiv y(modp) X ≡y(modp) Ax (modp)≠ay(modp)ax (modp) \neq ay(modp)ax (modp)=ay(modp). Note: X,y⊂Xx, Y \subset Xx,y⊂ x

    So in the end, all the elements in Y are different, and since all the elements in Y are mod p, all the elements in Y are between [0,p−1][0, p-1][0,p−1] and different. X = Y

So there are:


1 x 2 x 3 x … ( p – 1 ) = ( a x 1 ) ( m o d p ) x ( a x 2 ) ( m o d p ) x … x [ a x ( p – 1 ) ] ( m o d p ) 1\times2\times3\times\cdots(p-1)=(a\times1)(modp)\times(a\times2)(modp)\times\cdots\times[a\times(p-1)](modp)

According to the multiplication operation of modulus, there are:


1 x 2 x 3 x … ( p – 1 ) ≡ a p – 1 [ 1 x 2 x 3 x … x ( p – 1 ) ] ( m o d p ) 1\times2\times3\times\cdots(p-1) \equiv a^{p-1}[1\times2\times3\times\cdots\times(p-1)](modp)

( p – 1 ) ! ≡ a p – 1 ( p – 1 ) ! ( m o d p ) (p-1)! \equiv a^{p-1}(p-1)! (modp)

According to the division of the modular arithmetic, because the GCD (I, p) = 1, I ⊂ [0, 1 p -] the GCD (I, p) = 1, the I \ subset [0, 1] p the GCD (I, p) = 1, I ⊂ [0, 1 p -], so there are:


1 ≡ a p – 1 ( m o d p ) 1 \equiv a^{p-1}(modp)

a p – 1 ≡ 1 ( m o d p ) a^{p-1} \equiv 1(modp)

So that’s the end of proving Fermat’s little theorem.

3. Euler function and Euler theorem

Euler function definition: The number less than n and mutually prime with n is called the Euler function ϕ(n)\phi(n)ϕ(n)

Euler’s theorem: for any interprime integers A and N, there is aϕ(n)=1modna^{\phi(n)}=1 modna ϕ(n)=1modn, ϕ(n)\phi(n)ϕ(n) is a Euler function.

Proof of Euler’s theorem: time is short, later fill.

The greatest common divisor theorem

If two integers a and b, d= GCD (a,b)d= GCD (a,b)d= GCD (a,b), then there are integers x and y where ax+by=dax+by=dax+by=d. If a and B are interprime, then ax+by=1ax+by=1ax+by=1 ax+by=1

Conclusion:

These theorems need to remember, in the back of the STUDY of RSA asymmetric encryption algorithm used a lot, from the beginning of the meng forced to write after the clear thinking, perhaps this is the charm of learning, see more practice more summary!

Reference article:

www.cnblogs.com/gambler/p/9…

latex.vimsky.com/

Mirukuchan. Making. IO/post/fermat…