暗号化

最近暗号化の論文を再読しました。課題は有名なアルゴリズムに使われている計算式,Block Ciphers、です。
Block ciphers are a class of encryption/decryption algorithms which use a single key and the same cipher function to encrypt a block consisting of multiple bits. This contrasts which a stream cipher, which encrypts one bit at a time and varies the cipher between bits. In a block cipher, the same key may be used for all blocks in a message (this is known as an electronic code book cipher). However, there are other techniques in which the key of one block depends on the ciphertext of preceding blocks. This prevents the existence of multiple blocks of the same plaintext which map to the same ciphertext (allowing an attacker to possibly guess the key from context). e.g. If the same block of eight bytes repeats frequently, an 8-letter word that might appear in that context could be guessed, allowing a known-plaintext attack to be undertaken.
Algebraic operations used in ciphers include: bitwise OR, addition mod n, shifts mod n, exclusive OR, and cyclic shifts (<<<,>>>). For example 110>>>2 = 101.
Block cipher encryption and decryption can be written formulaically as:
E: PxK->C
D: CxK->P
As the same key is utilized for both encryption and decryption, the cipher is known as a "symmetric key cipher".
Two concepts essential to cipher design are confusion and diffusion. Confusion involves ensuring that the bits of ciphertext are not linearly related to bits of plaintext and the key. For example, the function C=(P XOR K0)+K1 would cause confusion. There is no way to infer the key bits from either one or two known plaintexts.
Diffusion involves ensuring that every bit of ciphertext is related to every bit of plaintext and every bit of the key. This can be accomplished by shifts and an iterative round function. For example: C=r(r(r(P,K1),K2),K3), where the round function is r(x,k)=(x+k)<<<3. With each successive round, output bits become more dependent on input bits. Note that the above iteration involves diffusion if and only if the round function moves the bits. In this case, x[i-3],x[i-2],x[i-1] bits are moved to x[i], x[i+1], and x[i+2] positions (where the positions are from right to left increasing) on the first iteration. On the second iteration, the i-3 bit of the output above is combined with the i-3 bit of the key to yield the round two output's i bit. Note that the i bit of round two's output thus depends on the i-6 bit of the input plaintext and the i-3 and i-6 bits of the key. So many bits of the key are likely to be used. This does not seem to be a case of diffusion involving multiple bits of X, though.
A specific type of cryptanalysis is the algebraic attack. A cipher susceptible to this is a 2-round version of the STEA(Simplified Tiny Encryption Algorithm) cipher:
P=(L0,R0) C=(L2,R2) L2=L0+(R0 XOR K1) R2=R0+(L2 XOR K2)
Using algebra, the subkeys can be deduced:
K1=(L2-L0)XOR R0
K2=(R2-R0) XOR L2
So the key can be recovered with knowledge of a single plaintext/ciphertext pair. Note that the addition mod n (marked plus) is nonliear, according to the paper. This appears to be because of either a. the modularity (x+2 mod 5 yields (3,4,0) for (1,2,3)) or b. the fact that in each round a different key is added (but x+2+3+4 would still be linear if no modularity were used, so this is probably not the reason).