（注：本文仅供学习，转载或者拷贝引起的一切后果自负，本文部分内容翻译并参考自：《An Introduction to Mathematical Cryptography》（Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman））
本文将介绍一些基于格问题上的困难问题的公钥密码体制。回顾下实数域R上的向量空间V，线性空间上的两个向量可以相加或者乘以实数。格与向量空间非常相似，不同之处在于，运算是在格上。这个很小的差别引出了一系列很有意思的问题。在介绍格密码之前，首先介绍2个密码体制，同余公钥体制（A congruential public key cryptosystem）和背包公钥密码体制（Subset-sum problems and knapsack cryptosystems）。
一、同余公钥密码体制
（1）Alice选择一个大整数p（公共参数，大家都知晓）和两个秘密整数f,g，f,g满足：
这里需要注意的是，f,g都小于q。Alice的私钥是f,g。公钥是大整数h，q。
（2）Bob为了发送消息m给Alice，选择一个随机的整数r，明文m和r需要满足下面的等式。
接下来Bob计算密文
（3）Alice接收到密文m后进行解密。
Alice计算下面的公式
再计算
（注意，
下面给出正确性证明：
只需要证明b==m即可。
根据加解密过程，我们有：
由于f,g,r的大小都有范围限制，所以有：
因此，当Alice计算
这是该算法的关键之处，最后Alice计算
下面给出该密钥体制的JAVA实现。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.Random;
public class CongruentialPublicKey {
private static BigInteger Q, H, F, G;
public BigInteger[] generatorQandH() {
int alpha = 50;
BigInteger g;
Random r = new Random();
BigInteger q = null;
while (true) {
q = BigInteger.probablePrime(alpha, r);
if (q.bitLength() != alpha)
continue;
if (q.isProbablePrime(10)) // if q is prime ,contiune
{
Q = q.multiply(new BigInteger("2")).add(BigInteger.ONE);
if (Q.isProbablePrime(10)) // if p is prime,then break
break;
}
}
while (true) {
g = BigInteger.probablePrime(Q.bitLength() - 1, r);
if (!g.modPow(BigInteger.ONE, Q).equals(BigInteger.ONE)
&& !g.modPow(q, Q).equals(BigInteger.ONE)) {
break;
}
}
// Q = new BigInteger("122430513841");
// 选择随机的F和G作为密钥
BigInteger max = Q.divide(new BigInteger("2"));
boolean flag_exit = true;
F = (new BigDecimal(Math.random() + "").multiply(new BigDecimal(max)))
.toBigInteger();
// F = new BigInteger("231231");
while (flag_exit) {
if ((F.pow(2).subtract(max)).signum() < 0) {
flag_exit = false;
} else {
F = (new BigDecimal(Math.random() + "")
.multiply(new BigDecimal(F))).toBigInteger();
}
}
BigInteger min = Q.divide(new BigInteger("4"));
flag_exit = true;
G = (new BigDecimal(Math.random() + "").multiply(new BigDecimal(Q)))
.toBigInteger();
// G = new BigInteger("195698");
while (flag_exit) {
if (G.pow(2).subtract(max).signum() < 0
&& G.pow(2).subtract(min).signum() > 0
&& F.gcd(G).equals(BigInteger.ONE)) {
flag_exit = false;
} else if (G.pow(2).subtract(max).signum() > 0)// only 满足这个
{
G = (new BigDecimal(G)).multiply(
new BigDecimal(Math.random() + "")).toBigInteger();
} else if (G.pow(2).subtract(min).signum() < 0)// 仅仅满足这个
{
G = (new BigDecimal(G)).divide(
new BigDecimal(Math.random() + ""), 0).toBigInteger();
}else if(!F.gcd(G).equals(BigInteger.ONE))//保证F,G互素
{
G = (new BigDecimal(G)).multiply(
new BigDecimal(Math.random() + "")).toBigInteger();
}
}
// 计算公钥H
H = F.modInverse(Q).multiply(G).mod(Q);
BigInteger[] temp = new BigInteger[2];
temp[0] = Q;
temp[1] = H;
return temp;
}
public BigInteger encrypt(BigInteger m) {
BigInteger e;
BigInteger r = (new BigDecimal(F)).multiply(
new BigDecimal(Math.random() + "")).toBigInteger();
// r = new BigInteger("101010");
e = r.multiply(H).add(m).mod(Q);
return e;
}
public BigInteger decrypt(BigInteger e) {
BigInteger a = F.multiply(e).mod(Q);
// System.out.println(F.gcd(G));
BigInteger b = (F.modInverse(G).multiply(a)).mod(G);
return b;
}
public static void main(String args[]) {
CongruentialPublicKey cpk = new CongruentialPublicKey();
BigInteger[] PublicKey = cpk.generatorQandH();
System.out.println("Alice：随机产生的公钥（q,h）：(" + PublicKey[0] + ","
+ PublicKey[1] + ")");
// Bob发送消息
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.println("Bob：请输入要发送的明文：");
try {
String str;
BigInteger m = null;
while ((str = br.readLine()) != null) {
m = new BigInteger(str);
if (m.pow(2).subtract(PublicKey[0].divide(new BigInteger("2")))
.signum() < 0) {
break;
} else {
System.out.println("您输入的明文过大，请重新输入！");
}
}
System.out.println(cpk.decrypt(cpk.encrypt(m)));
} catch (IOException e) {
e.printStackTrace();
}
}
}
代码运行结果如下：
（注明：本代码只针对一定范围内的大整数，对于较大的字符串，可以分段处理，笔者在这里不再讨论。有兴趣的读者可以自己尝试下实现，难度不大。）
下一篇，笔者将介绍另一个有趣的问题--背包公钥密码体制。
笔者水平有限，难免存在不足，欢迎批评交流！