Paillier算法分析
本文參考知乎上一篇關于paillier算法的分析,糾正了一點錯誤,推理過程更加詳細。
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLiAzNfRHLGZkRGZkRfJ3bs92YsYTMfVmepNHLwElaOp3a65EMNpHW4Z0MMBjVtJWd0ckW65UbM5WOHJWa5kHT20ESjBjUIF2X0hXZ0xCMx81dvRWYoNHLrdEZwZ1Rh5WNXp1bwNjW1ZUba9VZwlHdssmch1mclRXY39CXldWYtlWPzNXZj9mcw1ycz9WL49zZuBnLzAjMxMTMzUTM1EzNwEjMwIzLc52YucWbp5GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.png)
證明:
因為
λ = l c m ( p − 1 , q − 1 ) λ = lcm(p-1,q-1) λ=lcm(p−1,q−1)
是以
p − 1 ∣ λ , q − 1 ∣ λ = > λ = a ( p − 1 ) = b ( q − 1 ) p-1|λ ,q-1|λ => λ = a(p-1) = b(q-1) p−1∣λ,q−1∣λ=>λ=a(p−1)=b(q−1)
由費馬小定理可得
g λ = g a ( p − 1 ) ≡ 1 m o d p = > p ∣ g λ − 1 g^λ=g^{a(p-1)}\equiv1modp => p|g^\lambda-1 gλ=ga(p−1)≡1modp=>p∣gλ−1
同理
g λ = g b ( q − 1 ) ≡ 1 m o d p = > q ∣ g λ − 1 g^λ=g^{b(q-1)}\equiv1modp => q|g^\lambda-1 gλ=gb(q−1)≡1modp=>q∣gλ−1
因為p、q互素【見定理1】
是以
p q ∣ g λ − 1 = > n ∣ g λ − 1 = > g λ ≡ 1 m o d n = > g λ = k 1 n + 1 pq|g^\lambda-1 => n|g^\lambda-1 => g^\lambda\equiv1modn => g^\lambda=k_1n+1 pq∣gλ−1=>n∣gλ−1=>gλ≡1modn=>gλ=k1n+1
同理
r λ = k 2 n + 1 r^\lambda=k_2n+1 rλ=k2n+1
c λ = ( g m r n ) λ m o d ( n 2 ) = g m λ m o d ( n 2 ) . r n λ m o d ( n 2 ) = ( k 1 n + 1 ) m m o d ( n 2 ) . ( k 2 n + 1 ) n m o d ( n 2 ) c^\lambda=(g^mr^n)^\lambda mod(n^2)=g^{m\lambda}mod(n^2).r^{n\lambda}mod(n^2)=(k_1n+1)^mmod(n^2).(k_2n+1)^nmod(n^2) cλ=(gmrn)λmod(n2)=gmλmod(n2).rnλmod(n2)=(k1n+1)mmod(n2).(k2n+1)nmod(n2)
有以下性質
( k n + 1 ) m o d ( n 2 ) = k n + 1 ( k n + 1 ) 2 m o d ( n 2 ) = 2 k n + 1 ( k n + 1 ) 3 m o d ( n 2 ) = 3 k n + 1 . . . ( k n + 1 ) m m o d ( n 2 ) = m k n + 1 (kn+1)mod(n^2) =kn+1\\ (kn+1)^2mod(n^2) =2kn+1\\ (kn+1)^3mod(n^2) =3kn+1\\ ...\\ (kn+1)^mmod(n^2) =mkn+1 (kn+1)mod(n2)=kn+1(kn+1)2mod(n2)=2kn+1(kn+1)3mod(n2)=3kn+1...(kn+1)mmod(n2)=mkn+1
是以
c λ = ( m k 1 n + 1 ) m o d ( n 2 ) . ( k 2 n 2 + 1 ) m o d ( n 2 ) = ( m k 1 n + 1 ) m o d ( n 2 ) c^\lambda=(mk_1n+1)mod(n^2).(k_2n^2+1)mod(n^2)=(mk_1n+1)mod(n^2) cλ=(mk1n+1)mod(n2).(k2n2+1)mod(n2)=(mk1n+1)mod(n2)
是以
L ( c λ m o d ( n 2 ) ) L ( g λ m o d ( n 2 ) ) = m k 1 n n k 1 n n = m \frac{L(c^\lambda mod(n^2))}{L(g^\lambda mod(n^2))}=\frac{\frac{mk_1n}{n}}{\frac{k_1n}{n}}=m L(gλmod(n2))L(cλmod(n2))=nk1nnmk1n=m
加法同态性質分析
對明文 m 1 m_1 m1和 m 2 m_2 m2加密後,分别得到
E ( m 1 ) = g m 1 r 1 n m o d ( n 2 ) E ( m 2 ) = g m 2 r 2 n m o d ( n 2 ) E(m_1)=g^{m_1}r_1^nmod(n^2)\\ E(m_2)=g^{m_2}r_2^nmod(n^2)\\ E(m1)=gm1r1nmod(n2)E(m2)=gm2r2nmod(n2)
那麼
E ( m 1 ) . E ( m 2 ) = g ( m 1 + m 2 ) ( r 1 . r 2 ) n = E ( m 1 + m 2 ) E(m_1).E(m_2) = g^{(m_1+m_2)}(r_1.r_2)^n=E(m_1+m_2) E(m1).E(m2)=g(m1+m2)(r1.r2)n=E(m1+m2)
證明過程使用到的定理:
1.費馬小定理:
2.定理1
3.定理2