Preface
虽说依旧是paper题- -但出题人基本没做隐藏or变换（coin考点crash，然后回来骂骂咧咧.jpg，笑死
RSA
[题解分析]
Encode
1 | from Crypto.Util.number import * |
Attack on r ($e_{i},n_{i},c_{i}$)s with Common d($d<N_{r}^{\delta}$)
https://www.ijcsi.org/papers/IJCSI-9-2-1-311-314.pdf
$N_{1}<N_{2}<…<N_{r}<2N_{1}$ with Common $d<N_{r}^{\delta}$. And all each modulus is balanced so that $s=p+q-1<\frac{3\sqrt{2}}{2}N_{r}^{1/2}<3N^{1/2}.$ Then we have r equations: $e_{i}d-N_{i}k_{i}=1-k_{i}s_{i}$.
Let vector A = $[d,k_{1},k_{2}…,k_{r}]$, $M=ceil(N_{r}^{1/2})$, matrix B =
$C=AB=[dM,1-k_{1}s_{1},1-k_{2}s_{2},…,1-k_{r}s_{r}]$.
转求向量C满足Lattice(B)的Minkowski界的条件（满足即转化为SVP）：
$|C|<N_{r}^{\frac{1}{2}+\delta}\sqrt{1+9r}$.
$\sqrt{r+1}det(B)^{\frac{1}{r+1}}>\sqrt{r+1}N_{1}^{\frac{r+\frac{1}{2}}{r+1}}>\sqrt{r+1}(\frac{N_{r}}{2})^{\frac{r+\frac{1}{2}}{r+1}}$.
Then we wanna $N_{r}^{\frac{1}{2}+\delta}\sqrt{1+9r}<\sqrt{r+1}(\frac{N_{r}}{2})^{\frac{r+\frac{1}{2}}{r+1}}\Leftrightarrow N_{r}^{\delta-\frac{r}{2r+2}}<\frac{\sqrt{\frac{r+1}{9r+1}}}{2^{\frac{2r+1}{2r+2}}}$.
Cuz $r\geq 1$, the right side $>\frac{1}{6}$. So if
the Minkowski satisfies.
作本题的简单估计，$bound\approx\frac{3}{8}-\frac{1}{400}>\frac{380}{1024}$.
size(d) = 385时，从原理上有一定失败几率，但能很容易交互出size(d)满足Minkowski界的d. (e.g. size(d)=380)
[exp]
1 | e = [...] |
Lattice
[题解分析]
考察Attack on NTRU Cryptosystem
NTRU - Nth Degree Truncated Polynomial Ring Units
$R=Z[x]/(x^{n}-1)$: quotient
$0^{th}$ step. Variable and Func prepared
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39n =
d =
q =
PR = PolynomialRing(ZZ, name = 'x')
x = PR.gen()
R = PR.quotient_ring(x ^ n - 1, names = 'y')
y = R.gen()
# return an n-coef polynomial where exactly d coef are nonzero(±1)
def random_poly():
assert(d <= n)
result = n * [0]
for i in range(d):
while True:
r = randrange(n)
if not result[r]:
break
result[r] = 1 - 2 * randrange(2)
return R(result)
# balance coef between -q/2 and q/2 (mod q)
def balance_mod(f, q):
g = list(((f[i] + q // 2) % q) - q // 2 for i in range(n))
return R(g)
# return h which f*h=p*u+1
def invert_mod_prime(f, p):
T = R.base().change_ring(Integers(p)).quotient(x ^ n - 1)
return R(1 / T(f))
# return h which f*h=q*u+1 (q=2^m, m\in N*)
def invert_mod_powerof2(f, q):
assert(q.is_power_of(2))
g = invert_mod_prime(f, 2)
while True:
r = balance_mod(f * g, q)
if r == 1:
return g
g = balance_mod(g * (2 - r), q)$1^{st}$ step. Key Generation
Select a prime p and genkey with the func below,
1
2
3
4
5
6
7
8
9
10
11
12
13
14p =
def genkey():
while True:
try:
f = random_poly()
fp = invert_mod_prime(f, p)
fq = invert_mod_powerof2(f, q)
break
except:
pass
g = random_poly()
pubkey = balance_mod(p * g * fq, q)
prikey = f, fp
return pubkey, prikey$2^{nd}$ step. Encryption
1
2
3def enc(m, pubkey):
r = random_poly()
return balance_mod(pubkey * r + m, q)$3^{rd}$ step. Decryption
1
2
3
4def dec(c, prikey):
f, fp = prikey
a = balance_mod(c * f, q)
return balance_mod(a * fp, p)Explain why it works,
On Zmod(q), $c=hr+m=pgfqr+m$.
$a=cf=pg(ffq)r+fm=pgr+f*m$.
$afp=pgrfp+(ffp)m$, and it equals to m on Zmod(p).
当$pgr+fm$在Zmod(q)上和ZZ上完全等价，或是说该多项式系数均落在$(-q/2,q/2)$时，解密可行性成立，个人做粗略参数估计后发现应满足$2d(p+1)<q$（有paper上给出*p(6d+1)<q，但证明暂时没时间看ojz）
下再给出针对NTRU的攻击：
On Zmod(q), $h=pgfq=p*g/f$.
Let $hp=pp^{-1}g/f$, so we have $g=f*hp$.
f’s coef $\in \{-1,0,1\}$, this means g is obtained as a combination of the polys $q,qx,qx^{2},…,qx^{n-1},hp,hpx,hpx^{2},…,hp*x^{n-1}$.
Assume $hp=\sum a_{i}x^{i}$,
对上述格子作规约，SVP得到的向量如果呈现g的{0, 1, -1}特性且检验通过，则攻击成功
以$R(AL[0][n:])$作为f进行dec.
[exp]
1 | from Crypto.Util.number import * |