《数论算法》 第五章 原根与离散对数
? 私有密钥是x
(二) ElGamal加密算法
? 将明文信息M表示成{ 0, 1, …, p－1 }范围内的数 ? 加密:
– 秘密选择随机数k， 计算： – a≡gk（mod p） – b≡Myk（mod p） – 密文为(a, b) ? 解密:
– M≡bax（mod p） 其中除法ba表示乘法bax??x?1
（原理：因ax?gkx（mod p），故bax≡ykMax≡gxkMgxk≡M（mod p）） （不足：信息有扩张） (三) 例
?① 生成密钥：使用者A选取素数p＝2357及Z2357的生成元g＝2，A选取私钥x＝1751并计算公钥
y≡gx（mod p）≡21751（mod 2357）≡1185 A的公钥是p＝2357， g＝2， y≡1185
② 加密：为加密消息M＝2035， 消息的发送方B选取一个随机整数
k＝1520 并计算
a≡gk（mod p）≡21520≡1430（mod 2357）
45/58
《数论算法》 第五章 原根与离散对数
b≡Myk（mod p）≡2035×11851520≡697（mod 2357） （其中yk（mod p）≡11851520≡2084（mod 2357）） B发送（a, b）＝（1430, 697）给A ③ 解密：A计算
a?x≡ap?1?x≡14302357?1?1751≡1430605≡ 872 (mod
2357)
M≡bax≡ba?x≡697×872 ≡2035 (mod 2357) (四) ElGamal加密算法安全性
? 复杂度：攻击ElGamal加密算法等价于解离散对数问题 ? 要使用不同的随机数k来加密不同的信息
– 假设用同一个k来加密两个消息M1，M2，所得到的密文分别为?a1,b1?和?a2,b2?，则b1/b2＝M1/M2，故当M2已知时，M1可以很容易地计算出来。即
M1≡M2b1/b2
同理
M2≡M1b2/b1
? 例如，已知p＝2357，g＝2，x＝1751，y≡1185（mod 2357）
选 k＝1520，则消息M1＝2035的密文为(a1,b1)＝(1430，
697) 还选 k＝1520，消息M2＝100的密文为(a2,b2)＝(1430，984)
消息M3＝1000的密文为(a3,b3)＝(1430，
412)
那么，设已知M1＝2035，则有
46/58
《数论算法》 第五章 原根与离散对数
M2≡M1b2/b1≡2035×984×697－1≡100（mod 2357）
M3≡M1b3/b1≡2035×412×697－1≡1000（mod 2357） （其中697－1≡700（mod 2357）） 5. 6. 3 改进的随机数生成算法
利用同余运算生成伪随机数的Lehmer算法（也称线性同余法（LCGS））： n＝1, 2, …
同时讨论了其安全性。该算法的循环周期T严重依赖于乘数a、增量c和种子值X0的选择。其实质在于
Xn?aXn?1+c?modm?，
Xn?aX0?nc?an?1?a?1（mod m）
即每个Xn完全由m、a、c及X0决定。故算法关键是如何确定参数m、a、c和X0。
【定理5.6.1】（Hull和Dobell）由Lehmer算法生成的随机数列为满周期数列的充分必要条件是 （ⅰ）?c,m?＝1；
（ⅱ）若存在素数q，使得qm，则必有qa?1； （ⅲ）若4m，则必有4a?1。 （证）（略）。
条件（ⅰ）意味着c和m互素。 条件（ⅱ）是指
?a?a?q??＝1
?q??a即若k??q??，则可得
a?1?qk
其中q为m的素因数。
47/58
《数论算法》 第五章 原根与离散对数
由条件（ⅲ），若m4为整数，可设
获得满周期或足够长的周期是对所有随机数生成算法的重要考量指标之一。其中较常见的有混合线性同余法（Mixed LCGS，选c＞0）和乘法线性同余法（Multi plicative LCGS，c＝0）。
（1）混合线性同余法
对于c＞0，有可能使得周期T=m。此处仅讨论如何选择m。 为得到尽可能大的周期，以及在（0, 1）区间内的高密度的随机数un?Xnm，故希望m尽可能大。其次，利用除以m而获得余数，是一项十分缓慢的算法操作。故为了避免这种除法
b操作，较好的选择是m=2，其中b为计算机用于存放实际数值的字长，这样就就能够利用整数溢出来避免这种明显的除以m的操作。
可供选用的混合线性同余法有 （a）（b）
Xn?515Xn?1?1?mod235?a?1?4t
；
。
Xn?314159269Xn?1?453806246?mod231?（2）乘法线性同余法
本方法的优点在于不需要c（c＝0）。由于条件（ⅰ）不能满足，因而不能达到满周期。但仍可以适当选择m与a，使T?m?1。此方法是比较有效的方法，也是线性同余法中被采用得较多的方法。
Hutchinson建议m取小于2b的最大素数p。那么，对于素数p而言，可以证明，如果a是以p为模的素因数，则周期T?p?1。显然，这只要选a为p的原根，且?X0,p?＝1即可，这时在每一个循环里，严格地获得每个整数1, 2, …, p?1各一次，而且选X0为从1至p?1之间的任意整数，都能保证T?p?1。这种方法称为素数模乘法线性同余法（PMMLCGs）。
48/58