密码学SAT入门文献0——Using Walk-SAT and Rel-SAT for cryptographic key search

本人的组织架构：

第2节 介绍一些关于密码学和数据加密标准的基本知识； 

第3节 讨论了编码的特点；

第4节 用Walk-SAT和Rel-SAT进行实验分析；

第6节 新的挑战；

第7节 对论文进行总结。

1 Introduction

2 Cryptography and DES

[Schneier, 1994] B. Schneier.Applied Cryptography:Protocols,Algorithms, and Source Code in C. John Wiley & Sons, 1994.

位向量P(明文) C(密文) K(秘钥)。

Search can be cut down if the cryptanalyst knows a sufficient number of blocks of plaintext with the corresponding ciphertext (known plaintext attack). This is a reasonable hypothesis: almost all messages and files have fixed parts. Using a network of 12 workstation and 247 (randomly generated) plaintexts, Matsui [1994a] broke DES in 50 days.

译文：如果密码分析人员知道足够多的带有相应密文的明文块(已知明文攻击)，则可以减少搜索。

译文：这是一个合理的假设:几乎所有的消息和文件都有固定的部分。使用12个工作站和247个(随机生成的)明文网络，Matsui [1994a]在50天内打破了DES。

 As the reader might now want to know how DES works, we start by saying that DES is a block cipher, which encipher blocks (sequences) of 64 bits into blocks of 64 bits using a key of 56 bits'. DES and almost all symmetric ciphers are built following an architecture which is due to Feistel and his group [Feistel et al., 1975]. After some initial preprocessing, the following operations are executed:

1. break the plaintext in two halves,

2. combine one half with the key using a clever function,

3. XOR the combination with the other half

4. swap the two parts.

These 4 operations constitutes a round and are repeated a suitable number of times. Figure 1 exemplifies the idea.