老师今天特意强调了考试，并且讲解了这些题，让人很难不怀疑......!!
在这里每道题都认真研究一下，做个记录
RSA
Adapted RSA with CRT
- (a)
很明显，就不多赘述了 - (b)
由于 \(g_1=g^{r_1(p-1)}\)
有 \(g_1\equiv g^{r_1(p-1)}\pmod(p)\)，根据费马小定理，\(g_1\equiv 1\pmod{p}\)，即 \(g_1-1\equiv 0\pmod{p}\)
所以 \(p|(g_1-1)\)
我们计算 \(\gcd(g_1-1, N)\)- 若 \(\gcd(g_1-1, N)=p\)
这样，我们成功的找到了 \(N\) 的 factorization，破解 \(m\) 易如反掌 - 若 \(\gcd(g_1-1, N)=pq=N\)
这意味着 \(g_1-1\equiv 0\pmod{q}\)
- 若 \(\gcd(g_1-1, N)=p\)
RSA with reused \(m, e\)
Bob 用不同的 \(e_1, e_2\) 加密了相同的信息 \(m\)，其中 \(\gcd(e_1, e_2)=1\)
Eve 截获了这两条密文 \(c_1=[m^{e_1}\mod N], c_2=[m^{e_2}\mod N]\)
请在不找出 \(N\) 的 factorization 的情况下破解 \(m\)
根据 裴蜀定理 (Bezout Identity)，我们有 \(Xe_1+Ye_2=\gcd(e_1, e_2)=1\)
且，通过扩展欧几里得定理可以找到满足条件的一组 \(X, Y\)
计算 \(c_1^Xc_2^Y \mod N\) 即可破解 \(m\):
\(c_1^Xc_2^Y\equiv m^{Xe_1}m^{Ye_2}\equiv m^{Xe_1+Ye_2}\equiv m\pmod{N}\)
More generally, if Bob encrypts a single message using several exponents \(e_1, e_2,...,e_n\), then Eve can recover the plaintext if \(\gcd(e_1, e_2, ..., e_n)=1\).
The moral is that Alice should use at most one encryption exponent for a given modulus.
Public Key Encryption
Adapted El Gamel Encryption
这道题没见过真有点想不出来吧......
- 发现 \(c_2=h^r+m_b\) 使用了 \(+\)，不属于 \(G\) 的群运算，因此 it's not necessary that \(c_2\in G\)
- 然而，由于 \(h^r\in G\)，我们能够保证 \([c_2-m_b\mod{p}]\in G\)
- 根据题意 \(p-1=2q\)，即 \(|\Z_p^*|=2|G|\) (这来自结论：对于奇质数 \(p\) 与集合 \(\{1,2,...,p-1\}\)，集合中模 \(p\) 的二次剩余与二次非剩余数量相等)
又 \([c_2-m\mod{p}] \in \Z_p^*\) (严格来说是 \(\Z_p\)，但是 \([c_2-m\mod{p}]=0\) 不可能成立)
因此，对于随机的 \(m\)，\([c_2-m\mod{p}]\in G\) 的概率是 \(1/2\) - 对于敌手输出的 \(m_0, m_1\)，挑战者选择加密 \(m_b\):
那么 \(\Pr[[c_2-m_b\mod{p}]\in G]=1\), 而 \(Pr[[c_2-m_{1-b}\mod{p}]\in G]=1/2\) (\(m_{1-b}\) 是随机选取的) - 敌手只需要分别计算上式，若 \([c_2-m_0\mod{p}]\in G\)，输出 \(0\); 若 \([c_2-m_1\mod{p}]\in G\)，输出 \(1\); 若两者都 \(\in G\)，则输出一个 random guess
敌手获得胜利的概率是 \(\Pr[\mathtt{PubK}^{\mathtt{eav}}_{\Pi, \mathscr{A}}(n)=1]=1/2+1/2\times 1/2=3/4\)
\(3/4\) 并不是一个可忽略的概率，因此这个加密方案不是 CPA-secure 的
One-way Function
Hard-Core Predicates and Pseudorandom Generators
之前提过，one-way function 并不能保证部分信息的泄露，其就算有硬核谓词也只保证有一部分信息不会泄露
\(G(x_1, x_2)\) 很明显是一个单向函数:
前半部分保证了 \(x_1\) 的单向性 (硬核谓词 \(hc(x_1, x_2)\) 只能从单向函数 \(g\) 上下手了)
后半部分是 \(n/2\) 个连续的 \(0\)，保证了 \(x_2\) 的信息绝不会被泄露 (结果根本就与 \(x_2\) 无关)
然而，由于这 \(n/2\) 个 \(0\) 的存在，可以很容易将其与 random string 区别开，因此其不能作为 PRG