• The Decision Diffie-Hellman problem. D. Boneh, ANTS 3, 1998
  Talks about various assumptions related to Diffie Hellman.
• Universal Hash Proofs and a Paradigm for Adaptive Chosen Ciphertext Secure Public-Key Encryption. R. Cramer and V. Shoup, Eurocrypt 2002
• Chosen-Ciphertext Security from Identity-Based Encryption. D. Boneh, R. Canetti, S. Halevi, and J. Katz, SICOMP 2007
  Uses a general mechanism called Identity Based Encryption which very surprisingly it turns out to actually gives us chosen ciphertext security almost for free.
• The Twin Diffie-Hellman Problem and Applications David Cash1 Eike Kiltz2 Victor Shoup3
• Efficient Chosen-Ciphertext Security via Extractable Hash Proofs Hoeteck Wee?
  Gives a very general framework for building chosen ciphertext ciphertext secure systems using extractable hash proofs.

• Who chosen ciphertext security matters, V.Shoup, 1998
  A nice paper by Victor Shoup that talks about why chosen cipher text security is so important in the public key settings. So if the Bleichenbacher attack wasn’t convincing enough, there are many other attacks like this that are possible if you don’t use a chosen cipher-text secure system.
• Twenty years of attacks on the RSA cryptosystem, D.Boneh, Notices of the AMS, 1999
• OAEP reconsidered, V.Shoup, Crypto 2001
• Key length, A.Lenstra, 2004
  A nice paper by Arjen Lenstra that discusses how you should choose key lengths for your public key systems, and even for your symmetric key systems.

前言

MIT6.824 是一门久负盛名的分布式系统课程，今天开始我将会将课程中的系统作业、学习感悟写在专栏 MIT6.824 Labs 中，与大家一起学习这门非常有趣的课程

前言

这次我们的任务是求离散对数 (discrete log)，采用的方法是 meet in the middle

Meet in the middle 最令我们印象深刻的就是其在破解 3DES 时的表现，将暴力破解的时间复杂度减少到了 $2 ^ {56}$

Overview

本章的主要内容是密钥交换 (key exchange) 和数论 (number theory)

密钥交换部分先后讲了 TTP (Trusted third parties), Merkle Puzzle 和 Diffie-Hellman protocol

数论部分的核心概念是 Modular arithmetic，并由此展开 Fermat’s theorem, Euler’s theorem 等定理，同时辅以 order, generator 等概念来做 Modular arithmetic

Overview

Fermat’s little theorem states that if $p$ is a prime number, then for any integer $a$, the number $a^p - a$ is an integer multiple of $p$. In the notation of modular arithmetic, this is expressed as

To be continued

Reference

• Fermat’s little theorem
• Proof of Fermat’s Little Theorem

一个新的专栏： Fun with number theory。这个专栏将从费马小定律开始，讲一些简单的数论知识，并介绍这些数论知识在公钥密码学、素数检查、复数计算等方面的应用

由于本人也是初学者，错误及遗漏之处还请大家多多指正

使用 lisp 编程的时候括号是一个很让人头疼的问题，vim 自带的 matchparen 可以起到一定的帮助，但是还是有两个小问题：

• 需要将光标移到括号上才能知道它对应的是哪个括号
• 频繁报错，很影响编码效率

在这里向大家推荐两个插件帮大家更舒服地编写 lisp

• Mer Puzzles are Optimal, B.Barak, M.Mahmoody-Ghidary, Crypto ‘09
  当我们只使用 symmetric ciphers 和 hash functions 的时候，Merkle Puzzles 是 key exchange 的最优选择。即我们无法在这样的限制下超越 quadratic gap
• On Formal models of key exchange (sections 7-9) V.Shoup, 1999

概览

此题出自 SICP 第一章练习题 1.13

题目

Prove that $Fib(n)$ is the closest integer to $\phi^n/\sqrt5$, where $\phi=(1+\sqrt5)/2$. Hint: Let $\psi=(1-\sqrt5)/2$. Use induction and definition of the Fibonacci numbers (see section 1.2.2) to prove that $Fib(n)=(\phi^n-\psi^n)/\sqrt5$.

概述

Counting change 问题来源于 SICP 第一章 1.2 节，书中给出了树形递归解法，并将迭代解法作为了课后练习。本文将会详细解答此题的迭代解法并给出运行时间的对比。

If art interprets our dream, the computer executes them in the guise of programs!
– Alan J. Perlis

前言

SICP 从 lisp 语法开始，为我们构成了一个包含计算机理论学科的闭环系统。今天开始我们要借助这本书更深入地理解程序的本质，

这次我们的目标是利用 Padding oracle attack 破解加密过的消息，padding oracle attack 的原理相对来讲比较简单，但是在具体的编程破解过程中需要注意几个问题：

• 发送 chosen ciphertext 的间隔时间不能太短，不然会收到 500 响应
• 在第一个字节被成功 decrypt 之后，可根据 padding 格式跳过一些字节，节省一些时间
  Read more »

我们可以从 Padding oracle attack 中找到伪造密文的思路：
设：$1 \oplus x = 5$, IV 中的对应字节为 $y$
则：当 $y’ = y \oplus x$ 时，$y \oplus 1 \equiv y’ \oplus 5$
所以：将 $y$ 更改为 $y’$ 可使 message 中的相应字节变更为 5

• Cryptographic Extraction and Key Derivation: The HKDF Scheme. H.Krawczyk, Crypto 2010
• Deterministic Authenticated-Encryption: A Provable-Security Treatment of the Keywrap Problem. P.Rogaway, T.Shrimption, Enrocrypt 2006
  Read more »

• The Order of Encryption and Authentication for Protecting Communications, H.Krawczyk, Crypto 2001.
  比较了 encrypt-then-MAC 和 MAC-then-encrypt
• Authenticated-Encryption with Associated-Data, P.Rogaway, Proc. of CCS 2002.
  讨论了 OCB
  Read more »

本周的任务是实现对大文件的分块哈希，使得浏览器可以在仅收到一部分文件的时候进行 MAC 校验（假设初始 MAC 已通过可信赖的途径分发给浏览器）

这周的习题比较简单，不需要过多讲解

• J.Bloack, P.Rogaway: CBC MACs for Arbitray-Length Messages: The Three-Key Constructions. J.Cryptology 18(2):111-131 (2005)
  讲了 CMAC 的基础构型：three key construction
• K.Pietrzak: A Tight Bound for EMAC. ICALP (2) 2006: 168-179
  证明了 CBC-MAC 的超集是 PRF
  Read more »

这次我们的任务是实现 CBC 和 CTR，要求用 AES 做为 PRF，所以我们只需要使用 AES 的加密算法。