ComSec & Crypto 综述
Symmetric Ciphers
Symmetric Cipher Model 对称算法模型
对于对称算法来说重要的概念
Plaintext 明文
Encryption algorithm 加密算法
Secret key
Ciphertext 密文
Decryption algorithm 解码算法 $\rightarrow$ 本质上是加密算法的reverse 从密文中获取明文
对于传统的起保护作用的加密算法有两个需要
- 我们需要一个强大的加密算法 最少 需要当你的对手知道你的算法并且能获得一个以上密文 的情况下也无法获得密钥或者破译密文。
- 发送方和接收方都需要有密钥的副本并且需要保证密钥的安全。如果对手知道你的算法并获取了你的密钥，那么使用这个密钥加密的对话会对其透明。
对称加密模型
X 代表明文 K代表密钥
For encryption, a key of the form $K = [k1,k2,…kj]$ is generated, if the key is generated at the meesage source then it must also be provided to the destination by means of some secure channel.Alternatively, a third party could generate the key and securely deliver it to both source and destination
在编码端 密钥被产出，并安全的递送给接收端。(也可以让第三方接手)
Y 代表密文
其中 $Y = E(K,X)$,
表示编码算法E 将明文X用K加密，得到密文Y
在信道里，想要，并且持有密钥的接收者，能够逆转这个信息
$X = D(K,Y)$
表示解码算法D 将密文Y用K解码， 得到明文X
**对刚刚的模型，在密码分析的角度(攻破密码) Cryptanalyst(图的上方)**：
相反，得到Y 但没有X或者K，并且想要得到X或者K或都要。并且 我们假定 你的对手持有加密算法E和解码算法D
如果只想要这一个密文的内容，就要分析X，如果想要阅读之后的消息，则需要恢复出密钥K。
密码学 Cryptography
密码学有着以下的3个独立的维度
- The type of operations used for transforming plaintext to ciphertext
所有的编码算法都基于两种原理 ：
substitution 替换，某个元素被替换成明文中其他的元素，相当于交换位置(不会出现明文里没有的元素)
transposition 调换，将明文的元素重排
这两种原理的特征就是$\Rightarrow$所有的操作都是可逆的(no info be lost)
- The number of keys used
如果接收和发送双方都使用同样的密钥，这个密码系统偏向于传统加密算法(对称加密算法)。如果使用不同的密钥，则偏向于asymmetric(非对称的)或者公钥算法
- The way in which the plaintext is processed (攻破密码系统)
Block Cipher 分组密码 ：每次放入一组元素，一组一组的加密。
Stream Cipher 流密码 ： 连续放入元素 一个个的加密。
公钥密码学
公钥密码
- 1976年 Diffie和Hellman在 《密码学新方法》提出
- 使用 公钥和私钥 $\rightarrow$ 解密和加密并非对称
- 利用数论的方法。 补充了对称密码
公钥密码的重要特点
- 仅根据 密码算法 和 加密密钥 无法确定解密密钥
- 两个密钥中的任何一个可以加密 而另一个解密
RSA
- 1977 来自MIT的 Rivest，Shamir & Adleman
- 是最著名 应用最广泛的公钥加密体制
- 明文和密文是 0-n-1 之间的整数，n的大小通常为 1024位 或者 309位十进制
RSA描述
$加密： C = M^e mod N, (0\leq M <N ) $
$解密： M = C^d mod N$
公钥$\rightarrow$ (e,N) ; 私钥 $\rightarrow$ (d,N)
其中$M^{ed}=MmodN$()
计算M^e 和 C^d 比较容易 ，但由e和n确定n 是不可行的
Hash
Hash 函数
Hash 并不用来 encryption / decryption 但在密码学中具有重要的价值
Hash 函数：任意长度的报文 $\rightarrow$ HASH $\rightarrow$ 较短的 定长的 报文
Hash函数的目的是为 报文等分组数据 产生 “数字指纹”
对Hash 函数的要求
- H 可以用于任意大小的 数据分组 并且 一定产生定长输出
- 对于任意的 x，H(x) 要容易计算 (比AES更容易)
- 单向性 ： 对于任意给定的码y， 寻求 x 使得 H(x) = y 在计算上不可行 [即value $\Rightarrow$ key 不可行]
- 弱抗碰撞性： 任意给定分组 x 寻求不等于x 的 x2 使得 H(x) = H(x2) 在计算上不可行 (在班上找和某人 生日相同的人)
- 强抗碰撞性：找到任意一组 (x1, x2) 使得H(x1) = H(x2) 在计算上不可行 (在一个班级找任意两个 生日相同的人)
- 碰撞 $\rightarrow$ 两个不等的 x 对应同一个 H(x) 在安全学中 我们需求碰撞 不发生
弱碰撞和强碰撞相比 强碰撞非常容易发生(与 生日悖论的原理相同)， 因为弱碰撞指定了x
Keccak
- 使用了海绵结构 可以 被视为轻量级密码
- 压缩函数 只使用了 XOR ｜ ROT(移位) 无查表和算术运算 $\rightarrow$ 速度 更快
Sponge construction
全0起手 每次吸收一个m
包括absorbing phase和Squeezing phase 「吸收和挤压阶段」
- algorithm Theta
- 每个字中的每一位新的值 $\rightarrow$ 当前值 前一列每个字的相同位 后一列每个字的邻接位(移位)
- 对 C[x] = XOR_i |L[x, i]|
- L[x, y] = L[x, y] XOR C[x - 1] XOR ROT(C[x + 1], 1)
- algorithm Rho
- 除了L[0, 0]外 每个字的内部使用循环移位进行置换 移位值为 (t+1)(t+2)/2 mod 64 「t 使得 [x, y] = M^t *[1, 0]^T」 t不是移位值 是找移位值的根据
- algorithm Pi
- 字之间进行5x5矩阵 置换 L[0,0] 不变
- L[x, y] = L[x1, y1] 其中(x, y ) = M * (x1, y1);
- algorithm Chi
- 每个字的 每一位新值 取决与 当前值 ｜ 同行的下一个字 的对应位 ｜ 相同行的下下个字的对应位 [循环]
About MPC, Homomorphic Encryption & CrypTen
MPC Secure multi-party computation
MPC的概念最初是由姚期智教授提出来的，Goldreich等人对其进行了深入研究，奠定了MPC的理论基础。Goldwasser与Cramer认为MPC是密码学中一个极其重要且强有力的工具。对于隐私数据共享的巨大需求使得MPC受到密码学界的高度重视并发展成为解决各种隐私保护问题的关键技术。
Multiparty Computation (MPC) is a research area within cryptography whose application is generally limited to preserving the privacy of participants to a conversation from each other, rather than to preventing eavesdropping by an outsider.
MPC 用到的三种安全模型： 理想模型(全是好人) ，半诚实模型(不破坏规则，但会推理出额外信息)，恶意模型
在无可信第三方的情况下，如何安全的计算一个约定函数(这可能有点像diffie Hellman)
Zero-Knowledge Proof 不向验证者提供有效信息的情况下使验证者相信你的论断
differential privacy 差分隐私 「利用噪声来实现安全(计算上安全)，而非加密手段」
可以拿出以下这个例子： 两个百万富翁比财产(他们不想让任何人知道自己有多少钱)
假设两人的财富都是1kw ～ 10kw 拿来10个编号的箱子，编号代表kw数(比如3kw 就是3号箱)，甲会对这10个箱子，每一个的编号对应的钱数 少于自己的 放入苹果，和自己一样的，放入香蕉，多于自己的，放入梨。 然后将10个箱子寄给乙。 乙选出自己对应财富的箱子，并销毁其他的箱子和编号。 这时打开箱子，甲和乙就能知道谁更富有。
「这个例子 基于半诚实模型，同时也有不经意传输 Obivious Transfer的影子, 即发送方向接收方发送信息中的一个部分，接收方可以正确的接收到信息，但不知道这个信息属于整体的哪个部分」
- MPC的两种应用形式： 外包计算 / 多方计算
- MPC需要确保输入数据的独立性、传递数据的准确性、计算过程的正确性，同时不能将个人的隐私数据泄露给其他参与者。MPC主要是针对在没有可信第三方时保密计算所有参与者约定的一个函数的情况，它在数字签名、电子拍卖、秘密共享等场景中有着重要的作用。
多方安全计算主要通过以下四大技术来进行保障:
（1）同态加密（Homomorphic Encryption，简称HE）
同态加密是一类具有特殊自然属性的加密方法， 可在密文域下进行数据运算的加密算法。 与一般加密算法相比， 同态加密除了能实现基本的加密操作之外， 还能实现密文间的多种计算功能， 即先计算后解密等价于先解密后计算。
（2）混淆电路（Garbled Circuit，简称GC）
混淆电路思想是利用计算机模拟集成电路的方式来实现多方安
全计算的， 它将运算任务转化为门电路的形式， 并且对每一条线路进行加密， 在很大程度上保障了用户的隐私安全。
（3）不经意传输（Oblivious Transfer，简称OT）
不经意传输协议是一种可保护隐私的秘密协议， 它使得服务发送方和服务接收方以不经意的方式交互信息， 从而可达到保护隐私的目的。 不经意传输协议是一个两方安全计算协议， 接收方从发送方的数据中选取部分数据， 协议使得接收方除选取的内容外， 对剩余数据一无所知， 并且发送方也无从知道被选取的内容。
（4） 秘密分享（Secret Sharing，简称SS）
秘密分享也被称为秘密分割， 是一种对秘密信息的管理方式， 它将秘密进行拆分， 拆分后的每一个分片由不同的参与者管理， 单个参与者无法恢复秘密信息， 需要超过一定门限数量的人一同协作进行合并才能恢复秘密文件。
Homomorphic Encrytion
对密文进行特定形式的代数运算后 仍然是加密的结果，这样解密得到的结果和明文进行同样的运算结果一样。 也就是说，这项技术能够在 数据加密的情况下进行诸如 检索、比较等操作，并且得出正确的结果。 这项技术的意义就 是从根本上解决数据被委托给第三方时的保密问题。
同态加密在以往都只能实现部分操作，全同态加密的可行性是由09年 斯坦福大学的 Craig Gentry 的 《Fully Homomorphic encryption Using Ideal Lattices》一文中，从数学角度上证明了全同态加密的可行性。
个人比较欣赏Gentry教授的定义，简明扼要的点出了其中的关键
A way to delegate processing of your data, without giving away access to it.
$指定运算符\Delta,加密算法E,解密算法D, 同态加密满足以下条件: E(x\Delta y)=E(x)\Delta E(y)$
CrypTen
隐藏/获取明文：
CrypTen支持两种分享类型：arithmetic（ArithmeticSharedTensor）和binary(BinarySharedTensor)。
通过cryptensor()方法构造的MPCTensor中默认使用arithmetic分享类型。其中ArithmeticSharedTensor中实现了“add”，“sub”，“mul”，“matmul”等方法。明文获取：由于n方的PRZS.share的所有值相加为0。通过pytorch的reduce方式，sum所有节点的tensor.share即可恢复原始tensor。然后使用FixedPointEncoder将tensor解码
模型加密
CrypTen可以先读取pytorch的模型文件，将pytorch模型转化成onnx（Open Neural Network Exchange）文件，并进一步解读onnx文件来构造crypten_model（Graph类或是Module类。Graph继承Container，Container继承Module）调用crypten_model类即可完成对模型的各类操作。图2.3中的同态加密张量和安全加密张量还未实现或通过测试。图2.4演示了使用CrypTen加密模型的方法。