• 同态加密库，以及对几种不同的同态加密算法进行分析。
• 1.什么是同态加密算法？ 如果有一个加密函数 f , 把明文A变成密文A’, 把明文B变成密文B’，也就是说f(A) = A’ ，f(B) = B’ 。另外还有一个解密函数，能够将 f 加密后的密文解密成加密前的明文。 对于一般的加密...
• 同态加密 举一个简单的例子解释一下： (1)Alice有消息m，需要一个工具人Bob进行函数f(m)处理; (2)但是Alice不想要工具人Bob知道消息m，于是她将消息m加密，c=E(m,sk)把密文发送给Bob; (3)Bob对密文进行操作f（c)，将...
同态加密
举一个简单的例子解释一下：
(1)Alice有消息m，需要一个工具人Bob进行函数f(m)处理;
(2)但是Alice不想要工具人Bob知道消息m，于是她将消息m加密，c=E(m,sk)把密文发送给Bob;
(3)Bob对密文进行操作f（c)，将结果返回给Alice;
(4)Alice用私钥解密结果f(m)=D(f（c),sk)


展开全文
• 同态加密算法As our reliance on cloud infrastructure increases and our social interactions become increasingly dependent on the internet, we worry more about data breaches in activities like online ...
同态加密算法As our reliance on cloud infrastructure increases and our social interactions become increasingly dependent on the internet, we worry more about data breaches in activities like online conversations and storing personal information on the cloud. Fully homomorphic encryption is a form of encryption that can tackle security issues arising from these activites. 随着我们对云基础架构的依赖增加以及我们的社交互动越来越依赖互联网，我们更加担心在线对话和将个人信息存储在云中等活动中的数据泄露。 完全同态加密是一种加密形式，可以解决由这些活动引起的安全性问题。
Fully homorphic encryption is regarded as the Holy Grail of information security because it can protect the privacy of data while it is stored in the cloud or while it is in transit. At first glance, the word “homomorphism” might seem unfamiliar, but it is not! “Homo” means similar and “morphism” means change, and homomorphism consequently means a form-preserving map between 2 algebraic structures. Homomorphic encryption is a special method of encryption that allows mathematical operations on encrypted data rather than on its plaintext. This means one can perform these operations on the data and get the encrypted output without ever knowing what the data was. The significant property of this particular type of encryption to note is that decrypting the operated encrypted data should give the same output as operating on the plaintext itself. 完全同态加密被视为信息安全的圣杯，因为它可以保护存储在云中或传输中的数据的私密性。 乍一看，“同态”一词可能看起来并不熟悉，但事实并非如此！ “同态”表示相似，“同态”表示变化，因此，同态意味着两个代数结构之间的形式保留图。 同态加密是一种特殊的加密方法，它允许对加密数据而不是其明文进行数学运算。 这意味着人们可以在不知道数据是什么的情况下对数据执行这些操作并获得加密的输出。 要注意的这种特殊类型的加密的重要属性是，解密操作的加密数据应提供与对纯文本本身进行操作相同的输出。
Our current homomorphic encryption models are either partially homomorphic or fully homomorphic. Partially homomorphic models allow only a certain number of operations on the data (usually multiplication or division). On the other hand, fully homomorphic encryption allows you to perform multiple sequential operations on the data without exposing the meaning of the message. 我们当前的同态加密模型是部分同态或完全同态的。 部分同态模型仅对数据进行一定数量的运算(通常是乘法或除法)。 另一方面，完全同态加密使您可以在不暴露消息含义的情况下对数据执行多个顺序操作。
This diagram above is a simple demonstration on how homomorphic encryption works. It starts with a plaintext m, let’s assume it’s the name of someone in an organization Boogle “ALICE”. Let function f be decapitalizing the name. The goal is to be able to perform this function on the plaintext m without compromising the actual value of it, i.e. perform f on the value of the enc(m). So first you encrypt the message m into some value, let’s say 23225. This value is then transformed into some other value using some other function, e.g. f(x) = x + 75. The output is 23300, and this corresponds to another completely encrypted message which can be decrypted to give “Alice”. 上图是有关同态加密如何工作的简单演示。 它以纯文本m开头，我们假设它是Boogle“ ALICE”组织中某人的名字。 让函数f使名称大写。 目的是能够在不损害纯文本m的实际值的情况下对纯文本m执行此功能，即对enc(m)的值执行f。 因此，首先将消息m加密为某个值，例如23225。然后使用其他函数( 例如f(x)= x + 75)将此值转换为其他值。 输出为23300，它对应于另一个完全加密的消息，可以对其进行解密以提供“ Alice”。
This property is what allows homomorphic encryption to protect against privacy breaches. With increasing technological infrastructure comes an added necessity to secure it. In the current model of encryption we use when storing information on Amazon or Google provided cloud servers, the information must be decrypted on the server side before performing any operation on it before sending them back to the client for them to review the output. This clearly leaves security vulnerabilities because our information is being revealed at a point while it is being operated on. Homomorphic encryption allows your data to remain encrypted not only while it is at rest, but also while it is in transit and while it is being operated on. As a result, the server would never know what the actual information value was. 此属性使同态加密可以防止违反隐私的行为。 随着技术基础设施的增加，增加了对其进行保护的必要性。 在当前用于在Amazon或Google提供的云服务器上存储信息时使用的当前加密模型中，必须先在服务器端对信息进行解密，然后再对其执行任何操作，然后再将其发送回客户端以供他们查看输出。 这显然留下了安全漏洞，因为我们的信息在运行时的某个时刻被泄露。 同态加密使您的数据不仅在静止时，在传输过程中和在运行时都保持加密状态。 结果，服务器将永远不知道实际的信息值是多少。
An important property of homomorphic encryption to consider is that it is inherently malleable. A malleable encryption model means that any intruder can intercept the encrypted message, transform it into a different encrypted message, and then decrypt it into a plaintext that makes “sense”. This is generally considered unfavorable, because imagine a situation where one is trying to send private medical information about their blood type O, but then someone intercepts then alters it to a different type A. This is an example of why malleability can be looked down on. 要考虑的同态加密的一个重要属性是，它具有固有的延展性。 可延展的加密模型意味着任何入侵者都可以拦截加密的消息，将其转换为其他加密的消息，然后将其解密为纯文本，从而产生“感觉”。 通常认为这是不利的，因为设想一种情况，其中有人试图发送有关其O型血的私人医疗信息，但随后有人进行拦截，然后将其更改为另一种A型。这就是为什么可以低估延展性的一个示例。
However, homomorphic encryption models are supposed to be malleable! Take an example where you’re trying to add information to your blood type, from O to O+. When you encrypt your message and send it along the route, the system only sees your encrypted message, but it can still transform your message from O to O+ as wanted. In this case, malleable systems allow multiple parties, such as in cloud infrastructure, to act on your data without seeing it. 但是，同态加密模型应该具有延展性！ 举一个例子，您尝试添加信息到您的血型，从O到O +。 当您加密消息并沿路由发送时，系统只会看到加密的消息，但仍可以根据需要将消息从O转换为O +。 在这种情况下，可延展的系统允许多个方(例如云基础架构中的一方)对您的数据进行操作而不会看到它们。
部分同态方案 (Partial Homomorphic Schemes)
RSA Encryption is an example of a partially homomorphic scheme, specifically multiplicative. It selects 2 prime numbers a and b and sets n = a ⋅ b. It then selects y and z such that RSA加密是部分同态方案的一个示例，特别是乘法。 它选择2个质数a和b并设置n = a⋅b。 然后选择y和z
y ⋅ z ≡ 1 mod ϕ (N) y⋅z mod 1 mod ϕ(N)
This is called the modular inverse of y of z modulo ϕ (N). The ≡ operator symbolizes congruence and means that the product y ⋅ z and 1 have the same remainder when divided by ϕ (N). ϕ (N) is called the Euler’s totient function and counts the positive integers up to N that are relatively prime to N. 2 relatively prime integers a and b, or coprime integers, are said to be so if the only positive integer that divides them both is 1. This forms a ring of possible values. 这称为z模ϕ(N)的y的模逆。 ≡运算符表示同余，表示乘以(N)时，乘积y⋅z和1具有相同的余数。 ϕ(N)被称为欧拉totient函数，并且对直到N的正整数进行计数，该正整数相对于N相对于质数.2个相对质数整数a和b或共质数整数被称为是这样，如果将它们相除的唯一正整数两者均为1。这形成了可能值的环。
In this case, a and b are private and are only known by the sender and receiver whereas p and q are public. Taking this information, the encryption and decryption schemes become 在这种情况下，a和b是私有的，只有发送方和接收方才知道，而p和q是公共的。 利用此信息，加密和解密方案成为
Enc(x)=x^b mod(n) Enc(x)= x ^ b mod(n)
Dec(x)=y^a mod(n) Dec(x)= y ^ a mod(n)
You can prove the homomorphism by taking a and b as example messages. 您可以通过使用a和b作为示例消息来证明同态。
Enc(a) . Enc(b) = Enc(a . b) Enc(a)。 Enc(b)= Enc(a .b)
全同态算法 (Fully Homomorphic Algorithms)
Now fully homomorphic systems are ones in which any types of mathematical operations can be performed on the plaintext. Craig Gentry was the first to suggest that they could be theoretically possible. 现在，完全同态系统是可以在纯文本上执行任何类型的数学运算的系统。 Craig Gentry第一个提出理论上可行的建议。
In his thesis, he used the analogy of a jewelry shop owner. Lavinia is the jewelry shop owner, and she has employees that create jewelry from materials like diamond and gold. However, she’s afraid of her employees stealing these valuable items. To combat this, she creates a box with gloves attached to them. The employees can stick their hands into the box to create the jewelry, but cannot take anything out as only Lavinia has the key to open the box. 在他的论文中，他使用了珠宝店老板的比喻。 Lavinia是珠宝店的老板，她的员工使用钻石和黄金等材料制作珠宝。 但是，她担心员工会偷这些有价值的物品。 为了解决这个问题，她创建了一个带有手套的盒子。 员工可以将手伸入盒子中来制作珠宝，但不能取出任何东西，因为只有Lavinia才能打开盒子。
In this model, there is some noise in the morphic process. Each transformation adds more noise to the system, but this makes the model impractical as the system gets much slower. This necessarily means that Gentry’s scheme grows in complexity as more and more operations are performed. For example, one search using this scheme on Google’s search engine would increase computations by not millions, but trillion of times. 在此模型中，形态过程中存在一些噪声。 每次转换都会给系统增加更多的噪声，但是这会使模型变得不切实际，因为系统变得越来越慢。 这必然意味着随着执行越来越多的操作，Gentry的方案变得越来越复杂。 例如，在Google的搜索引擎上使用此方案进行的一次搜索将使计算量增加数百万倍而不是数百万倍。
However, despite this impracticality, this discovery at least shows that homomorphic encryption exists and proves that these schemes are possible, even if theoretically. 但是，尽管有这种不切实际的想法，但该发现至少表明存在同态加密，并且即使在理论上也证明了这些方案是可行的。
翻译自: https://medium.com/swlh/as-our-reliance-on-cloud-infrastructure-increases-drastically-and-the-internet-becomes-the-core-of-cd7a2871a76a同态加密算法
展开全文
• BGN同态加密算法的实现，C++代码
• 基于MapReduce的并行同态加密算法
• 基于RWLE假设的同态加密算法的实现，简单易懂，自己写的。
• ## 全同态加密算法

千次阅读 2016-12-20 17:18:23
同态加密算法 作者：admin 发布于：2015-03-31 15:41 浏览数 为确保云计算环境下用户数据的安全性，利用同态加密算法对数据和加密函敦的隐私保护功能，设计一种基于整数多项式环的全同态加密算法。该...

全同态加密算法

为确保云计算环境下用户数据的安全性，利用同态加密算法对数据和加密函敦的隐私保护功能，设计一种基于整数多项式环的全同态加密算法。该算法包括同态算法和重加密算法，前者针对明文数据进行加密，后者针对密文数据进行二次加密。

一、基于整数环的全同态加密算法

1、全同态加密算法发展现状及数据保护特点

全同态加密算法颠覆了传统意义下的加密模式（图1、图2），它是一种可以对密文进行操作但仍可以恢复明文的加密算法。算法设计的目的是：解决云环境下数据上传服务器端，Sever不可信，用户把私有数据加密上传服务器端。全同态加密算法最终实现：

这样用户可以把私有信息经过加密上传服务器端，享受云服务，但是服务器端并不能获得用户数据。因此全同态加密算法可针对用户的需求满足对加密信息和加密函数的保护，使得在整个传递过程当中始终保持加密状态。

加密信息的处理如图3所示，主要是对私有信息进行保护。Alice有私有的函数fA和私有的信息XA，Bob把私有信息yB用私有公钥pkB加密得到E(y)发送给Alice，Alice用自己的私有函数fA加密私有信息XA和E(yB)，由于同态性质，函数fA被隐藏，而Bob获得E(fA (XA，yB)）。Bob通过私有的私钥加密D(E(fA (XA，yB)））=fA (XA，yB)。

加密函数的处理如图4所示，主要是对私有的操作函数进行保护。Alice有私有的函数以，并用私有公钥pkA加密函数fA发送给Bob，Bob根据私有信息XB计算E(fA )(XB)，由于同态性质，因此隐藏了Bob的信息XB，得到E(fa(b))，并发送给Alice，Alice用私钥解密获得fA(XB)。

2、整数环全同态加密算法分析

由于理想格全同态加密算法复杂度高，且密文数据扩张不能得到解决，因此实用性不强。根据已有的理想格和整数全同态加密算法，设计基于Fp[x]的全同态加密算法。

同态算法具体如下：

KeyGen：对f(x)∈Fp[x]，选择随机的整数ai，ri∈Z，因此公钥pk=，对每个b，满足bi =aif(x)+ri，b最大。

Encryption：随机选择一个整数子集S∈{1，2，…，，z}，m∈{O，1}，随机选择r∈(_22p，22p)，密文ci= [m+2r+2∑i∈sbi]modbo。

Decryption：m=[cmodx]mod2

同态性性质：

(l)加法：给定公钥pk，密文Cl、C2，则：

(2)乘法：给定公钥pk，密文cl、C2，则：

其中，Lxl表示x向下取整；rxn表示x向上取整。

加解密正确性分析：

(l)设需要加密的明文信息为m=l或m=o，选择的函数为Z (x)，选择n+l个q和n+l个l，S={1，2，…，n）。

(2)计算n+l个bi，使得bo次数最高。

(3)加密明文信息朋，得到c=[m+2r+ 2∑i∈Sb]modbo。

(4)不妨设f取得s集合中的前k个bi。

(5)密文c可以写成：

(6)c是满足多项式形式的数据，即c=g(x)x+n。

重加密算法Evaluate具体如下：

Keygen：按照上述算法选择公钥pk和私钥sk，选择k，其中，尼是满足计算安全的大素数；p是同态算法中的Fp [x]，定义xp=[2k/p-1/2]，汉明重量为θ的多项式g(x)=∑gixi，θ为2个a的最大距离，Ci∈z n[o，2k+l)，使得∑iESCi=m(mod2k+J)，Yi=ci/2k，因此可以得出∑i#sci=mod2k+1，新私钥sk’=< g1，92，…，gn>。

Encryption：

输入：密文c，新公钥pk’；

输出：新密文c’= [c. Yi]mod2 0

Decryption：

输入：新密文c’；

输出：

整个算法的设计思路是通过多项式的次数、模运算、交互运算以达到混乱明文的作用。在设计过程中主要是考虑把问题的复杂性归结到离散子集求和问题，因此，选择多项式是该算法的关键环节，多项式的选择可以根据加密方对安全的要求程度决定，例如安全程度低可以选择f(x)=x+1，如果安全程度高可以通过提升f (x)的次数来加强。同态算法的设计还是延续了理想格方法和整数方法的特点，使得循环操作环节简单，便于实际应用。

性质基于整数环Fp[x]的全同态加密算法计算量是O(Y15)。

证明：在Evaluate运算中，需要确定xp、ci、Yi、Encryption和Decryption 5个部分，输入的pk={bl，b2，…，bn）有n个，需要计算量为n；c=m+2r+∑iES bi ]mod bo，计算量为n；加密运算和解密运算需要计算量为n；每个重加密运算都需要挖次操作，所以，计算量大约为：在实际应用中，存在匿名同态协议和一种半匿名，即相邻结点间不是匿名的，非相邻结点间是匿名的。另外还存在一个乐观可信第三方(optimistic trusted third party)，用于解决当出现非法访问时去找到那个非法访问者，该TTP只有在出现问题时才存在，所以不会影响效率。同态加密技术的快速发展，在云数据检索、投票、垃圾邮件过滤、信号分析领域都有着广泛的应用。在安全协议上，同态算法都是解决一些关键问题的有效方法和手段。

三、算法性能比较

全同态加密算法的主要优势是可以针对密文进行操作，仍然可以回复明文，因此，满足用户对云服务的基本要求。本文算法与2种全同态加密算法进行比较（表1）：

(1)理想格全同态加密算法：需要进行矩阵运算和向量模运算（向量的加法和乘法），每加密一个比特都需要进行矩阵和向量运算（表示为连续性不好），公钥扩展O(n7)，每个Evaluate中计算门的计算量为O(n6)。

(2)整数全同态加密算法：需要进行整数模运算，连续性好，Evaluate算法中输入超过本身算法要求，就不会实现全同态的性质，存在攻击危险。每个Evaluate中计算门的计算量为O(y13)。

(3)整数环全同态加密算法：主要进行多项式运算，加密过程中不需要重新选择多项式（连续性好），Evaluate中计算门的计算量为O(Y5)，根据实际安全的级别进行筛选。

在算法的设计环节，虽然没有保证严格雪崩效应，但是把算法的安全性依靠在离散子集求和这个难解问题，因此安全性没有受到影响，而且有更好的实现价值。今后需要对降低基于整数多项式环的全同态加密算法的时空开支以及明密文数据的扩散问题进行研究。


展开全文
• 面向云计算的混合同态加密算法研究.pdf
• paillier同态加密算法原理及代码实现
paillier同态加密算法原理及代码实现
由于工程量巨大，这里先贴上代码提醒自己还有这么个事情，等寒假有时间了再慢慢补充解析
代码实现
提前生成素数打表来提升算法速度，生成素数的代码点这里
注意：待加密字符串长度需为4的倍数且长度不超过12个字符；代码在实现同态加法的部分还存在问题需要修改
#include<stdio.h>
#include<iostream>
#include<fstream>
#include<iomanip>
#include <string>
#define len1 128
#define len2 2
using namespace std;

static int Primes[2800] =                         //前2800个素数
{
3,      5,      7,      11,     13,     17,     19,     23,     29,     31,
37,     41,     43,     47,     53,     59,     61,     67,     71,     73,
79,     83,     89,     97,     101,    103,    107,    109,    113,    127,
131,    137,    139,    149,    151,    157,    163,    167,    173,    179,
181,    191,    193,    197,    199,    211,    223,    227,    229,    233,
239,    241,    251,    257,    263,    269,    271,    277,    281,    283,
293,    307,    311,    313,    317,    331,    337,    347,    349,    353,
359,    367,    373,    379,    383,    389,    397,    401,    409,    419,
421,    431,    433,    439,    443,    449,    457,    461,    463,    467,
479,    487,    491,    499,    503,    509,    521,    523,    541,    547,
557,    563,    569,    571,    577,    587,    593,    599,    601,    607,
613,    617,    619,    631,    641,    643,    647,    653,    659,    661,
673,    677,    683,    691,    701,    709,    719,    727,    733,    739,
743,    751,    757,    761,    769,    773,    787,    797,    809,    811,
821,    823,    827,    829,    839,    853,    857,    859,    863,    877,
881,    883,    887,    907,    911,    919,    929,    937,    941,    947,
953,    967,    971,    977,    983,    991,    997,    1009,   1013,   1019,
1021,   1031,   1033,   1039,   1049,   1051,   1061,   1063,   1069,   1087,
1091,   1093,   1097,   1103,   1109,   1117,   1123,   1129,   1151,   1153,
1163,   1171,   1181,   1187,   1193,   1201,   1213,   1217,   1223,   1229,
1231,   1237,   1249,   1259,   1277,   1279,   1283,   1289,   1291,   1297,
1301,   1303,   1307,   1319,   1321,   1327,   1361,   1367,   1373,   1381,
1399,   1409,   1423,   1427,   1429,   1433,   1439,   1447,   1451,   1453,
1459,   1471,   1481,   1483,   1487,   1489,   1493,   1499,   1511,   1523,
1531,   1543,   1549,   1553,   1559,   1567,   1571,   1579,   1583,   1597,
1601,   1607,   1609,   1613,   1619,   1621,   1627,   1637,   1657,   1663,
1667,   1669,   1693,   1697,   1699,   1709,   1721,   1723,   1733,   1741,
1747,   1753,   1759,   1777,   1783,   1787,   1789,   1801,   1811,   1823,
1831,   1847,   1861,   1867,   1871,   1873,   1877,   1879,   1889,   1901,
1907,   1913,   1931,   1933,   1949,   1951,   1973,   1979,   1987,   1993,
1997,   1999,   2003,   2011,   2017,   2027,   2029,   2039,   2053,   2063,
2069,   2081,   2083,   2087,   2089,   2099,   2111,   2113,   2129,   2131,
2137,   2141,   2143,   2153,   2161,   2179,   2203,   2207,   2213,   2221,
2237,   2239,   2243,   2251,   2267,   2269,   2273,   2281,   2287,   2293,
2297,   2309,   2311,   2333,   2339,   2341,   2347,   2351,   2357,   2371,
2377,   2381,   2383,   2389,   2393,   2399,   2411,   2417,   2423,   2437,
2441,   2447,   2459,   2467,   2473,   2477,   2503,   2521,   2531,   2539,
2543,   2549,   2551,   2557,   2579,   2591,   2593,   2609,   2617,   2621,
2633,   2647,   2657,   2659,   2663,   2671,   2677,   2683,   2687,   2689,
2693,   2699,   2707,   2711,   2713,   2719,   2729,   2731,   2741,   2749,
2753,   2767,   2777,   2789,   2791,   2797,   2801,   2803,   2819,   2833,
2837,   2843,   2851,   2857,   2861,   2879,   2887,   2897,   2903,   2909,
2917,   2927,   2939,   2953,   2957,   2963,   2969,   2971,   2999,   3001,
3011,   3019,   3023,   3037,   3041,   3049,   3061,   3067,   3079,   3083,
3089,   3109,   3119,   3121,   3137,   3163,   3167,   3169,   3181,   3187,
3191,   3203,   3209,   3217,   3221,   3229,   3251,   3253,   3257,   3259,
3271,   3299,   3301,   3307,   3313,   3319,   3323,   3329,   3331,   3343,
3347,   3359,   3361,   3371,   3373,   3389,   3391,   3407,   3413,   3433,
3449,   3457,   3461,   3463,   3467,   3469,   3491,   3499,   3511,   3517,
3527,   3529,   3533,   3539,   3541,   3547,   3557,   3559,   3571,   3581,
3583,   3593,   3607,   3613,   3617,   3623,   3631,   3637,   3643,   3659,
3671,   3673,   3677,   3691,   3697,   3701,   3709,   3719,   3727,   3733,
3739,   3761,   3767,   3769,   3779,   3793,   3797,   3803,   3821,   3823,
3833,   3847,   3851,   3853,   3863,   3877,   3881,   3889,   3907,   3911,
3917,   3919,   3923,   3929,   3931,   3943,   3947,   3967,   3989,   4001,
4003,   4007,   4013,   4019,   4021,   4027,   4049,   4051,   4057,   4073,
4079,   4091,   4093,   4099,   4111,   4127,   4129,   4133,   4139,   4153,
4157,   4159,   4177,   4201,   4211,   4217,   4219,   4229,   4231,   4241,
4243,   4253,   4259,   4261,   4271,   4273,   4283,   4289,   4297,   4327,
4337,   4339,   4349,   4357,   4363,   4373,   4391,   4397,   4409,   4421,
4423,   4441,   4447,   4451,   4457,   4463,   4481,   4483,   4493,   4507,
4513,   4517,   4519,   4523,   4547,   4549,   4561,   4567,   4583,   4591,
4597,   4603,   4621,   4637,   4639,   4643,   4649,   4651,   4657,   4663,
4673,   4679,   4691,   4703,   4721,   4723,   4729,   4733,   4751,   4759,
4783,   4787,   4789,   4793,   4799,   4801,   4813,   4817,   4831,   4861,
4871,   4877,   4889,   4903,   4909,   4919,   4931,   4933,   4937,   4943,
4951,   4957,   4967,   4969,   4973,   4987,   4993,   4999,   5003,   5009,
5011,   5021,   5023,   5039,   5051,   5059,   5077,   5081,   5087,   5099,
5101,   5107,   5113,   5119,   5147,   5153,   5167,   5171,   5179,   5189,
5197,   5209,   5227,   5231,   5233,   5237,   5261,   5273,   5279,   5281,
5297,   5303,   5309,   5323,   5333,   5347,   5351,   5381,   5387,   5393,
5399,   5407,   5413,   5417,   5419,   5431,   5437,   5441,   5443,   5449,
5471,   5477,   5479,   5483,   5501,   5503,   5507,   5519,   5521,   5527,
5531,   5557,   5563,   5569,   5573,   5581,   5591,   5623,   5639,   5641,
5647,   5651,   5653,   5657,   5659,   5669,   5683,   5689,   5693,   5701,
5711,   5717,   5737,   5741,   5743,   5749,   5779,   5783,   5791,   5801,
5807,   5813,   5821,   5827,   5839,   5843,   5849,   5851,   5857,   5861,
5867,   5869,   5879,   5881,   5897,   5903,   5923,   5927,   5939,   5953,
5981,   5987,   6007,   6011,   6029,   6037,   6043,   6047,   6053,   6067,
6073,   6079,   6089,   6091,   6101,   6113,   6121,   6131,   6133,   6143,
6151,   6163,   6173,   6197,   6199,   6203,   6211,   6217,   6221,   6229,
6247,   6257,   6263,   6269,   6271,   6277,   6287,   6299,   6301,   6311,
6317,   6323,   6329,   6337,   6343,   6353,   6359,   6361,   6367,   6373,
6379,   6389,   6397,   6421,   6427,   6449,   6451,   6469,   6473,   6481,
6491,   6521,   6529,   6547,   6551,   6553,   6563,   6569,   6571,   6577,
6581,   6599,   6607,   6619,   6637,   6653,   6659,   6661,   6673,   6679,
6689,   6691,   6701,   6703,   6709,   6719,   6733,   6737,   6761,   6763,
6779,   6781,   6791,   6793,   6803,   6823,   6827,   6829,   6833,   6841,
6857,   6863,   6869,   6871,   6883,   6899,   6907,   6911,   6917,   6947,
6949,   6959,   6961,   6967,   6971,   6977,   6983,   6991,   6997,   7001,
7013,   7019,   7027,   7039,   7043,   7057,   7069,   7079,   7103,   7109,
7121,   7127,   7129,   7151,   7159,   7177,   7187,   7193,   7207,   7211,
7213,   7219,   7229,   7237,   7243,   7247,   7253,   7283,   7297,   7307,
7309,   7321,   7331,   7333,   7349,   7351,   7369,   7393,   7411,   7417,
7433,   7451,   7457,   7459,   7477,   7481,   7487,   7489,   7499,   7507,
7517,   7523,   7529,   7537,   7541,   7547,   7549,   7559,   7561,   7573,
7577,   7583,   7589,   7591,   7603,   7607,   7621,   7639,   7643,   7649,
7669,   7673,   7681,   7687,   7691,   7699,   7703,   7717,   7723,   7727,
7741,   7753,   7757,   7759,   7789,   7793,   7817,   7823,   7829,   7841,
7853,   7867,   7873,   7877,   7879,   7883,   7901,   7907,   7919,   7927,
7933,   7937,   7949,   7951,   7963,   7993,   8009,   8011,   8017,   8039,
8053,   8059,   8069,   8081,   8087,   8089,   8093,   8101,   8111,   8117,
8123,   8147,   8161,   8167,   8171,   8179,   8191,   8209,   8219,   8221,
8231,   8233,   8237,   8243,   8263,   8269,   8273,   8287,   8291,   8293,
8297,   8311,   8317,   8329,   8353,   8363,   8369,   8377,   8387,   8389,
8419,   8423,   8429,   8431,   8443,   8447,   8461,   8467,   8501,   8513,
8521,   8527,   8537,   8539,   8543,   8563,   8573,   8581,   8597,   8599,
8609,   8623,   8627,   8629,   8641,   8647,   8663,   8669,   8677,   8681,
8689,   8693,   8699,   8707,   8713,   8719,   8731,   8737,   8741,   8747,
8753,   8761,   8779,   8783,   8803,   8807,   8819,   8821,   8831,   8837,
8839,   8849,   8861,   8863,   8867,   8887,   8893,   8923,   8929,   8933,
8941,   8951,   8963,   8969,   8971,   8999,   9001,   9007,   9011,   9013,
9029,   9041,   9043,   9049,   9059,   9067,   9091,   9103,   9109,   9127,
9133,   9137,   9151,   9157,   9161,   9173,   9181,   9187,   9199,   9203,
9209,   9221,   9227,   9239,   9241,   9257,   9277,   9281,   9283,   9293,
9311,   9319,   9323,   9337,   9341,   9343,   9349,   9371,   9377,   9391,
9397,   9403,   9413,   9419,   9421,   9431,   9433,   9437,   9439,   9461,
9463,   9467,   9473,   9479,   9491,   9497,   9511,   9521,   9533,   9539,
9547,   9551,   9587,   9601,   9613,   9619,   9623,   9629,   9631,   9643,
9649,   9661,   9677,   9679,   9689,   9697,   9719,   9721,   9733,   9739,
9743,   9749,   9767,   9769,   9781,   9787,   9791,   9803,   9811,   9817,
9829,   9833,   9839,   9851,   9857,   9859,   9871,   9883,   9887,   9901,
9907,   9923,   9929,   9931,   9941,   9949,   9967,   9973,   10007,  10009,
10037,  10039,  10061,  10067,  10069,  10079,  10091,  10093,  10099,  10103,
10111,  10133,  10139,  10141,  10151,  10159,  10163,  10169,  10177,  10181,
10193,  10211,  10223,  10243,  10247,  10253,  10259,  10267,  10271,  10273,
10289,  10301,  10303,  10313,  10321,  10331,  10333,  10337,  10343,  10357,
10369,  10391,  10399,  10427,  10429,  10433,  10453,  10457,  10459,  10463,
10477,  10487,  10499,  10501,  10513,  10529,  10531,  10559,  10567,  10589,
10597,  10601,  10607,  10613,  10627,  10631,  10639,  10651,  10657,  10663,
10667,  10687,  10691,  10709,  10711,  10723,  10729,  10733,  10739,  10753,
10771,  10781,  10789,  10799,  10831,  10837,  10847,  10853,  10859,  10861,
10867,  10883,  10889,  10891,  10903,  10909,  10937,  10939,  10949,  10957,
10973,  10979,  10987,  10993,  11003,  11027,  11047,  11057,  11059,  11069,
11071,  11083,  11087,  11093,  11113,  11117,  11119,  11131,  11149,  11159,
11161,  11171,  11173,  11177,  11197,  11213,  11239,  11243,  11251,  11257,
11261,  11273,  11279,  11287,  11299,  11311,  11317,  11321,  11329,  11351,
11353,  11369,  11383,  11393,  11399,  11411,  11423,  11437,  11443,  11447,
11467,  11471,  11483,  11489,  11491,  11497,  11503,  11519,  11527,  11549,
11551,  11579,  11587,  11593,  11597,  11617,  11621,  11633,  11657,  11677,
11681,  11689,  11699,  11701,  11717,  11719,  11731,  11743,  11777,  11779,
11783,  11789,  11801,  11807,  11813,  11821,  11827,  11831,  11833,  11839,
11863,  11867,  11887,  11897,  11903,  11909,  11923,  11927,  11933,  11939,
11941,  11953,  11959,  11969,  11971,  11981,  11987,  12007,  12011,  12037,
12041,  12043,  12049,  12071,  12073,  12097,  12101,  12107,  12109,  12113,
12119,  12143,  12149,  12157,  12161,  12163,  12197,  12203,  12211,  12227,
12239,  12241,  12251,  12253,  12263,  12269,  12277,  12281,  12289,  12301,
12323,  12329,  12343,  12347,  12373,  12377,  12379,  12391,  12401,  12409,
12413,  12421,  12433,  12437,  12451,  12457,  12473,  12479,  12487,  12491,
12497,  12503,  12511,  12517,  12527,  12539,  12541,  12547,  12553,  12569,
12577,  12583,  12589,  12601,  12611,  12613,  12619,  12637,  12641,  12647,
12653,  12659,  12671,  12689,  12697,  12703,  12713,  12721,  12739,  12743,
12757,  12763,  12781,  12791,  12799,  12809,  12821,  12823,  12829,  12841,
12853,  12889,  12893,  12899,  12907,  12911,  12917,  12919,  12923,  12941,
12953,  12959,  12967,  12973,  12979,  12983,  13001,  13003,  13007,  13009,
13033,  13037,  13043,  13049,  13063,  13093,  13099,  13103,  13109,  13121,
13127,  13147,  13151,  13159,  13163,  13171,  13177,  13183,  13187,  13217,
13219,  13229,  13241,  13249,  13259,  13267,  13291,  13297,  13309,  13313,
13327,  13331,  13337,  13339,  13367,  13381,  13397,  13399,  13411,  13417,
13421,  13441,  13451,  13457,  13463,  13469,  13477,  13487,  13499,  13513,
13523,  13537,  13553,  13567,  13577,  13591,  13597,  13613,  13619,  13627,
13633,  13649,  13669,  13679,  13681,  13687,  13691,  13693,  13697,  13709,
13711,  13721,  13723,  13729,  13751,  13757,  13759,  13763,  13781,  13789,
13799,  13807,  13829,  13831,  13841,  13859,  13873,  13877,  13879,  13883,
13901,  13903,  13907,  13913,  13921,  13931,  13933,  13963,  13967,  13997,
13999,  14009,  14011,  14029,  14033,  14051,  14057,  14071,  14081,  14083,
14087,  14107,  14143,  14149,  14153,  14159,  14173,  14177,  14197,  14207,
14221,  14243,  14249,  14251,  14281,  14293,  14303,  14321,  14323,  14327,
14341,  14347,  14369,  14387,  14389,  14401,  14407,  14411,  14419,  14423,
14431,  14437,  14447,  14449,  14461,  14479,  14489,  14503,  14519,  14533,
14537,  14543,  14549,  14551,  14557,  14561,  14563,  14591,  14593,  14621,
14627,  14629,  14633,  14639,  14653,  14657,  14669,  14683,  14699,  14713,
14717,  14723,  14731,  14737,  14741,  14747,  14753,  14759,  14767,  14771,
14779,  14783,  14797,  14813,  14821,  14827,  14831,  14843,  14851,  14867,
14869,  14879,  14887,  14891,  14897,  14923,  14929,  14939,  14947,  14951,
14957,  14969,  14983,  15013,  15017,  15031,  15053,  15061,  15073,  15077,
15083,  15091,  15101,  15107,  15121,  15131,  15137,  15139,  15149,  15161,
15173,  15187,  15193,  15199,  15217,  15227,  15233,  15241,  15259,  15263,
15269,  15271,  15277,  15287,  15289,  15299,  15307,  15313,  15319,  15329,
15331,  15349,  15359,  15361,  15373,  15377,  15383,  15391,  15401,  15413,
15427,  15439,  15443,  15451,  15461,  15467,  15473,  15493,  15497,  15511,
15527,  15541,  15551,  15559,  15569,  15581,  15583,  15601,  15607,  15619,
15629,  15641,  15643,  15647,  15649,  15661,  15667,  15671,  15679,  15683,
15727,  15731,  15733,  15737,  15739,  15749,  15761,  15767,  15773,  15787,
15791,  15797,  15803,  15809,  15817,  15823,  15859,  15877,  15881,  15887,
15889,  15901,  15907,  15913,  15919,  15923,  15937,  15959,  15971,  15973,
15991,  16001,  16007,  16033,  16057,  16061,  16063,  16067,  16069,  16073,
16087,  16091,  16097,  16103,  16111,  16127,  16139,  16141,  16183,  16187,
16189,  16193,  16217,  16223,  16229,  16231,  16249,  16253,  16267,  16273,
16301,  16319,  16333,  16339,  16349,  16361,  16363,  16369,  16381,  16411,
16417,  16421,  16427,  16433,  16447,  16451,  16453,  16477,  16481,  16487,
16493,  16519,  16529,  16547,  16553,  16561,  16567,  16573,  16603,  16607,
16619,  16631,  16633,  16649,  16651,  16657,  16661,  16673,  16691,  16693,
16699,  16703,  16729,  16741,  16747,  16759,  16763,  16787,  16811,  16823,
16829,  16831,  16843,  16871,  16879,  16883,  16889,  16901,  16903,  16921,
16927,  16931,  16937,  16943,  16963,  16979,  16981,  16987,  16993,  17011,
17021,  17027,  17029,  17033,  17041,  17047,  17053,  17077,  17093,  17099,
17107,  17117,  17123,  17137,  17159,  17167,  17183,  17189,  17191,  17203,
17207,  17209,  17231,  17239,  17257,  17291,  17293,  17299,  17317,  17321,
17327,  17333,  17341,  17351,  17359,  17377,  17383,  17387,  17389,  17393,
17401,  17417,  17419,  17431,  17443,  17449,  17467,  17471,  17477,  17483,
17489,  17491,  17497,  17509,  17519,  17539,  17551,  17569,  17573,  17579,
17581,  17597,  17599,  17609,  17623,  17627,  17657,  17659,  17669,  17681,
17683,  17707,  17713,  17729,  17737,  17747,  17749,  17761,  17783,  17789,
17791,  17807,  17827,  17837,  17839,  17851,  17863,  17881,  17891,  17903,
17909,  17911,  17921,  17923,  17929,  17939,  17957,  17959,  17971,  17977,
17981,  17987,  17989,  18013,  18041,  18043,  18047,  18049,  18059,  18061,
18077,  18089,  18097,  18119,  18121,  18127,  18131,  18133,  18143,  18149,
18169,  18181,  18191,  18199,  18211,  18217,  18223,  18229,  18233,  18251,
18253,  18257,  18269,  18287,  18289,  18301,  18307,  18311,  18313,  18329,
18341,  18353,  18367,  18371,  18379,  18397,  18401,  18413,  18427,  18433,
18439,  18443,  18451,  18457,  18461,  18481,  18493,  18503,  18517,  18521,
18523,  18539,  18541,  18553,  18583,  18587,  18593,  18617,  18637,  18661,
18671,  18679,  18691,  18701,  18713,  18719,  18731,  18743,  18749,  18757,
18773,  18787,  18793,  18797,  18803,  18839,  18859,  18869,  18899,  18911,
18913,  18917,  18919,  18947,  18959,  18973,  18979,  19001,  19009,  19013,
19031,  19037,  19051,  19069,  19073,  19079,  19081,  19087,  19121,  19139,
19141,  19157,  19163,  19181,  19183,  19207,  19211,  19213,  19219,  19231,
19237,  19249,  19259,  19267,  19273,  19289,  19301,  19309,  19319,  19333,
19373,  19379,  19381,  19387,  19391,  19403,  19417,  19421,  19423,  19427,
19429,  19433,  19441,  19447,  19457,  19463,  19469,  19471,  19477,  19483,
19489,  19501,  19507,  19531,  19541,  19543,  19553,  19559,  19571,  19577,
19583,  19597,  19603,  19609,  19661,  19681,  19687,  19697,  19699,  19709,
19717,  19727,  19739,  19751,  19753,  19759,  19763,  19777,  19793,  19801,
19813,  19819,  19841,  19843,  19853,  19861,  19867,  19889,  19891,  19913,
19919,  19927,  19937,  19949,  19961,  19963,  19973,  19979,  19991,  19993,
19997,  20011,  20021,  20023,  20029,  20047,  20051,  20063,  20071,  20089,
20101,  20107,  20113,  20117,  20123,  20129,  20143,  20147,  20149,  20161,
20173,  20177,  20183,  20201,  20219,  20231,  20233,  20249,  20261,  20269,
20287,  20297,  20323,  20327,  20333,  20341,  20347,  20353,  20357,  20359,
20369,  20389,  20393,  20399,  20407,  20411,  20431,  20441,  20443,  20477,
20479,  20483,  20507,  20509,  20521,  20533,  20543,  20549,  20551,  20563,
20593,  20599,  20611,  20627,  20639,  20641,  20663,  20681,  20693,  20707,
20717,  20719,  20731,  20743,  20747,  20749,  20753,  20759,  20771,  20773,
20789,  20807,  20809,  20849,  20857,  20873,  20879,  20887,  20897,  20899,
20903,  20921,  20929,  20939,  20947,  20959,  20963,  20981,  20983,  21001,
21011,  21013,  21017,  21019,  21023,  21031,  21059,  21061,  21067,  21089,
21101,  21107,  21121,  21139,  21143,  21149,  21157,  21163,  21169,  21179,
21187,  21191,  21193,  21211,  21221,  21227,  21247,  21269,  21277,  21283,
21313,  21317,  21319,  21323,  21341,  21347,  21377,  21379,  21383,  21391,
21397,  21401,  21407,  21419,  21433,  21467,  21481,  21487,  21491,  21493,
21499,  21503,  21517,  21521,  21523,  21529,  21557,  21559,  21563,  21569,
21577,  21587,  21589,  21599,  21601,  21611,  21613,  21617,  21647,  21649,
21661,  21673,  21683,  21701,  21713,  21727,  21737,  21739,  21751,  21757,
21767,  21773,  21787,  21799,  21803,  21817,  21821,  21839,  21841,  21851,
21859,  21863,  21871,  21881,  21893,  21911,  21929,  21937,  21943,  21961,
21977,  21991,  21997,  22003,  22013,  22027,  22031,  22037,  22039,  22051,
22063,  22067,  22073,  22079,  22091,  22093,  22109,  22111,  22123,  22129,
22133,  22147,  22153,  22157,  22159,  22171,  22189,  22193,  22229,  22247,
22259,  22271,  22273,  22277,  22279,  22283,  22291,  22303,  22307,  22343,
22349,  22367,  22369,  22381,  22391,  22397,  22409,  22433,  22441,  22447,
22453,  22469,  22481,  22483,  22501,  22511,  22531,  22541,  22543,  22549,
22567,  22571,  22573,  22613,  22619,  22621,  22637,  22639,  22643,  22651,
22669,  22679,  22691,  22697,  22699,  22709,  22717,  22721,  22727,  22739,
22741,  22751,  22769,  22777,  22783,  22787,  22807,  22811,  22817,  22853,
22859,  22861,  22871,  22877,  22901,  22907,  22921,  22937,  22943,  22961,
22963,  22973,  22993,  23003,  23011,  23017,  23021,  23027,  23029,  23039,
23041,  23053,  23057,  23059,  23063,  23071,  23081,  23087,  23099,  23117,
23131,  23143,  23159,  23167,  23173,  23189,  23197,  23201,  23203,  23209,
23227,  23251,  23269,  23279,  23291,  23293,  23297,  23311,  23321,  23327,
23333,  23339,  23357,  23369,  23371,  23399,  23417,  23431,  23447,  23459,
23473,  23497,  23509,  23531,  23537,  23539,  23549,  23557,  23561,  23563,
23567,  23581,  23593,  23599,  23603,  23609,  23623,  23627,  23629,  23633,
23663,  23669,  23671,  23677,  23687,  23689,  23719,  23741,  23743,  23747,
23753,  23761,  23767,  23773,  23789,  23801,  23813,  23819,  23827,  23831,
23833,  23857,  23869,  23873,  23879,  23887,  23893,  23899,  23909,  23911,
23917,  23929,  23957,  23971,  23977,  23981,  23993,  24001,  24007,  24019,
24023,  24029,  24043,  24049,  24061,  24071,  24077,  24083,  24091,  24097,
24103,  24107,  24109,  24113,  24121,  24133,  24137,  24151,  24169,  24179,
24181,  24197,  24203,  24223,  24229,  24239,  24247,  24251,  24281,  24317,
24329,  24337,  24359,  24371,  24373,  24379,  24391,  24407,  24413,  24419,
24421,  24439,  24443,  24469,  24473,  24481,  24499,  24509,  24517,  24527,
24533,  24547,  24551,  24571,  24593,  24611,  24623,  24631,  24659,  24671,
24677,  24683,  24691,  24697,  24709,  24733,  24749,  24763,  24767,  24781,
24793,  24799,  24809,  24821,  24841,  24847,  24851,  24859,  24877,  24889,
24907,  24917,  24919,  24923,  24943,  24953,  24967,  24971,  24977,  24979,
24989,  25013,  25031,  25033,  25037,  25057,  25073,  25087,  25097,  25111,
25117,  25121,  25127,  25147,  25153,  25163,  25169,  25171,  25183,  25189,
25219,  25229,  25237,  25243,  25247,  25253,  25261,  25301,  25303,  25307,
25309,  25321,  25339,  25343,  25349,  25357,  25367,  25373,  25391,  25409
};

class BigNum
{
public:
int length;   //大数长度
int signal;   //大数符号
unsigned long array[len1];   //大数绝对值

BigNum();   //构造函数
BigNum(unsigned __int64);    //构造函数用于赋初始值
BigNum(string s);   //读入字符串
BigNum(BigNum const& A);   //复制大数，const保护了原对象的属性
~BigNum();   //析构函数
BigNum operator+(BigNum& A);   //运算符+重载
BigNum operator-(BigNum& A);   //运算符-重载
BigNum operator*(BigNum& A);   //运算符*重载
BigNum operator/(BigNum& A);   //运算符/重载
BigNum operator%(BigNum& A);   //运算符%重载
BigNum operator-(void);   //负号重载
int operator==(BigNum& A);   //等于号重载
int operator!=(BigNum& A);   //不等号重载
int Compare(BigNum const& A);    //比较两大数绝对值大小
void GeneratePrime(void);   //产生素数
int Rabin_Miller(void);   //拉宾米勒算法用于素数测试
void Random(int a);   //随机产生一个大数
void Random(BigNum A);   //随机产生一个小于A的大数
void print(void);   //输出大数
void printS(void);   //输出字符串
BigNum power_mod(BigNum& A, BigNum& B);   //模幂算法计算X^A mod B
BigNum ex_euclid(BigNum a, BigNum b);   //扩展欧几里德算法
};

/*构造函数*/
BigNum::BigNum()
{
length = 1;
signal = 0;
for (int i = 0; i < len1; i++)
array[i] = 0;
}

/*构造函数用于赋初始值,参数为64位无符号int*/
BigNum::BigNum(unsigned __int64 A)
{
signal = 0;
if (A <= 0xffffffff)
{
length = 1;
array[0] = (unsigned long)A;
}
else
{
length = 2;	//长度大于1，存两位
array[1] = (unsigned long)(A >> 32);
array[0] = (unsigned long)A;
}
for (int i = length; i < len1; i++)  //补充高位
array[i] = 0;
}

/*用于读入输入的要加密的字符串，大数的每一位是32位，可以存4个字符*/
BigNum::BigNum(string s)
{
for (int i = 0; i < s.size(); i++)
{
array[i / 4] <<= 8;
array[i / 4] |= s[i];   //按位或，将4个字符存到一个大数位里
}
length = (s.size() - 1) / 4 + 1;   //数组长度
}

/*用于复制大数*/
BigNum::BigNum(BigNum const& A)
{
length = A.length;
signal = A.signal;
for (int i = 0; i < len1; i++)
array[i] = A.array[i];
}

/*析构函数,撤销对象占用的内存之前完成一些清理工作*/
BigNum::~BigNum()
{}

/*运算符+重载，思路：两数符号相同时，和=加数当前位+被加数当前位+进位；
两位异号时，转化为减法运算*/
BigNum BigNum::operator+(BigNum& A)
{
BigNum SUM, D;   //B为两大数之和，D为中间变量
int C = 0;    //进位
unsigned __int64 sum;   //存储int型的和

if (signal == A.signal) //符号相同时
{
SUM.signal = signal;
if (length >= A.length)    //长度=两数最大长度+1
SUM.length = length + 1;
else
SUM.length = A.length + 1;
for (int i = 0; i < SUM.length; i++)  //和=加数当前位+被加数当前+进位
{
sum = (unsigned __int64)A.array[i] + (unsigned __int64)array[i] + C;
if (sum <= 0xffffffff)
C = 0;     //超过2^32-1,进位
else
C = 1;
SUM.array[i] = (unsigned long)sum;   //和当前位= (unsigned long)和
}
while (SUM.length > 1)    //消除最高位的0
if (SUM.array[SUM.length - 1] == 0)
SUM.length--;
else break;
}
else if (signal == 0)
{
D = -A;
SUM = (*this) - D;
}    //异号则转为减法运算
else
{
D = -(*this);
SUM = A - D;
}
return  SUM;
}

/*运算符-重载，思路：两数同号时，比较两数大小，被减数大时，如果sub=被减数当前位-上一个
借位小于减数当前位，那么当前位有借位，差=借位*0xffffffff+sub-减数当前位+借位；减数大时，
原理一样，交换减数和被减数位置，最后负号与被减数相反；两数异号时，转化成加法运算*/
BigNum BigNum::operator-(BigNum& A)
{
BigNum SUB, D;   //B为两数的差，D为中间变量
int F = 0, i;     //借位F
unsigned int sub;   //暂存被减数减去上一个借位的差

if (signal == A.signal) //符号相同时
{
if (Compare(A) == 0 || Compare(A) == 2) //当被减数大于等于减数
{
if (signal == 0)
SUB.signal = 0;      //符号判断
else
SUB.signal = 1;
for (i = 0; i < length; i++) {
sub = array[i] - F;    //差=被减数当前位-上一个借位
if (sub < A.array[i])
F = 1;    //如果差小于减数当前位 ,有借位
else
F = 0;
SUB.array[i] = 0xffffffff * F - A.array[i] + sub + F; //差的当前位
}
}
else //被减数小于减数,基本原理同上
{
if (signal == 0)    //符号判断
SUB.signal = 1;
else
SUB.signal = 0;
for (i = 0; i < A.length; i++)
{
sub = A.array[i] - F;
if (sub < array[i])
F = 1;   //向上借位
else
F = 0;
SUB.array[i] = 0xffffffff * F - array[i] + sub + F;
}
}
SUB.length = i;
while (SUB.length > 1)     //消除最高位的0
if (SUB.array[SUB.length - 1] == 0)
SUB.length--;
else break;
}
else   //如果异号,转为加法
{
D = -A;
SUB = (*this) + D;
}
return SUB;
}

/*运算符*重载，思路：两数同号时，积的符号为正，否则为负，积=当前位的积+进位*/
BigNum BigNum::operator*(BigNum& A)
{
BigNum PRO;   //B两大数的积
unsigned __int64 C = 0;      //进位C
unsigned __int64 pro;   //暂存两数当前位的积

if (signal == A.signal)     //判断符号
PRO.signal = 0;
else
PRO.signal = 1;
PRO.length = length + A.length;       //长度不超过两数长度和
for (int i = 0; i < A.length; i++)
{
for (int j = 0; j <= length; j++)  //积=当前位的乘积+进位
{
pro = (unsigned __int64)A.array[i] * (unsigned __int64)array[j] + C;
if ((unsigned __int64)PRO.array[i + j] + pro > 0xffffffff)   //判断有无进位
C = ((unsigned __int64)PRO.array[i + j] + pro) >> 32;
else
C = 0;
PRO.array[i + j] += (unsigned long)pro;   //当前位要加上上一次运算结果
}
}
while (PRO.length > 1)      //消除最高位的0
if (PRO.array[PRO.length - 1] == 0)
PRO.length--;
else break;
return PRO;
}

/*运算符/重载，思路：采用试商法，取被除数最高位（如果小于除数最高位则去前两位）
和除数最高位试商，商=被除数最高位/（除数最高位+1），余数=被除数-商*除数，将余数
作为新的被除数做下次运算，每次运算完商都移位，直到余数小于等于除数，等于除数时商+1，
单独考虑除数长度为1的情况*/
BigNum BigNum::operator/(BigNum& A)
{

BigNum X(*this), Y, Z, I(1);
int i, len;   //len移位
unsigned __int64 temp, div, mul;
unsigned long F = 0; //余数

if (A.length > 1)   //除数长度大于1时
{
while (X.Compare(A) == 0) //当被除数大于除数时
{
if (X.array[X.length - 1] > A.array[A.length - 1])  //被除数最高位大
{
len = X.length - A.length;   //商=被除数当前位/(除数当前位+1)
div = X.array[X.length - 1] / (A.array[A.length - 1] + 1);
}
else if (X.length > A.length) //被除数长度较长
{
len = X.length - A.length - 1;
temp = X.array[X.length - 1];
temp = (temp << 32) + X.array[X.length - 2]; //商=被除数前两位/(除数当前位+1)
if (A.array[A.length - 1] == 0xffffffff)div = (temp >> 32);
else div = temp / (A.array[A.length - 1] + 1);
}
else //相等,加1退出
{
Y = Y + I;
break;
}
Z = BigNum(div);      //暂时的商(大数)
Z.length += len;      //长度=原长+移位
for (i = Z.length - 1; i >= len; i--)
Z.array[i] = Z.array[i - len];
for (i = 0; i < len; i++)
Z.array[i] = 0;
Y = Y + Z;      //商=原商+暂商
Z = A * Z;
X = X - Z;   //求余数代入下一次运算
}
if (X.Compare(A) == 2)
Y = Y + I;     //相等+1返回
if (signal != A.signal)
Y.signal = 1;     //判断符号，异号为负
return Y;
}
else //除数长度等于1
{
if (X.length == 1)     //被除数长度也为1
X.array[0] = X.array[0] / A.array[0];
else {
for (int i = X.length - 1; i >= 0; i--)
{
div = F;
div = (div << 32) + X.array[i];    //被除数=余数+当前位
X.array[i] = (unsigned long)(div / A.array[0]);   //商
mul = (div / A.array[0]) * A.array[0];
F = (unsigned long)(div - mul);  //求余,再带入下次运算
}
if (X.array[X.length - 1] == 0)
X.length--;
}
return X;
}
}

/*重载运算符之求模，思路同除法重载*/
BigNum BigNum::operator%(BigNum& A)
{
BigNum Y(*this), Z, T;
int i, len;
unsigned __int64 temp, div, F = 0;

if (A.length > 1)  //除数长度大于1时
{
while (Y.Compare(A) == 0 || Y.Compare(A) == 2) {     //被除数大等于除数
div = Y.array[Y.length - 1];     // 被除数=被除数当前位
temp = A.array[A.length - 1];     // 除数=除数当前位
len = Y.length - A.length;    //移位
if ((div == temp) && (len == 0))  //长度相同首位相同,余数为差
{
Y = Y - A; break;
}
if ((div <= temp) && length) //被除数小于除数，被除数取前两位
{
len--;
div = (div << 32) + Y.array[Y.length - 2];
}
div = div / (temp + 1);    //下面原理同除法重载
Z = BigNum(div);
if (len)
{
Z.length += len;
for (i = Z.length - 1; i >= len; i--)Z.array[i] = Z.array[i - len];
for (i = 0; i < len; i++)Z.array[i] = 0;
}
T = A * Z;
Y = Y - T;
}
return Y;
}
else  //除数长度等于1时
{
if (length == 1)
F = array[0] % A.array[0];
else
for (int i = length - 1; i >= 0; --i)
{
F = (F << 32) | array[i];
F %= A.array[0];
}
return BigNum(F);
}
}

/*负号重载 */
BigNum BigNum::operator-(void)
{
BigNum Temp = *this;
Temp.signal = 1 - signal;
return Temp;
}

/*等于号重载 */
int BigNum::operator==(BigNum& A)
{
if (signal == A.signal)   //判断符号
return Compare(A) == 2;    //绝对值相等则返回两数相等
else
return 0;
}

/*不等号重载*/
int BigNum::operator!=(BigNum& A)
{
if (signal == A.signal)
return Compare(A) != 2;
else
return 0;
}

/* 比较两大数绝对值大小，1表示小于A，0表示大于A，2表示相等*/
int BigNum::Compare(BigNum const& A)
{
if (length > A.length)      //比较长度
return 0;
else if (length < A.length)
return 1;
else
{
for (int i = length - 1; i >= 0; i--)
{
if (array[i] > A.array[i])
return 0;
else if (array[i] < A.array[i])
return 1;
}
return 2;   //相等
}
}

/*随机产生一个大数0<=X<=2^(32*SLEN)-1*/
void BigNum::Random(int a)
{
int i;

signal = a;   //a传入的一般都是0
length = len2;
for (i = 0; i < len2; ++i)   //rand产生0-32767的数（16位长），两次生成随机数移位后的和
array[i] = rand() << 16 | rand();
array[len2 - 1] |= 1 << 31;  //确保大数为512位长
}

/*随机产生一个小于A的大数*/
void BigNum::Random(BigNum A)
{
int i;

signal = 0;
if (A.length > 1) //被比较数长度为1时仅生成1位
{
length = A.length - 1;
for (i = 0; i < length; ++i)
array[i] = rand() << 16 | rand();
}
else //生成的位数少于被比较数
{
length = 1;
array[0] = rand() << 16 | rand();
while (array[0] > A.array[0])
array[0] = rand() << 16 | rand();
}
}

/*拉宾米勒算法用于素数测试，思路：1、先和前1000个素数比较，提高判断效率；2、计算
r和m使得n-1=(2^r)*m；3、随机选择a，计算y=a^m(mod n)；4、如果y=1或者y=n-1，输出素数，
结束；5、for i=1 to r-1, y=y^2(mod n)，若y=1,输出合数，结束，否则i++；6、若y!=n-1,
输出合数，结束。*/
int BigNum::Rabin_Miller(void)
{
BigNum temp, X(*this), I(1), O(0), m, E(2), A, Y, T, C;
int r = 0;

for (int i = 0; i < 2800; i++) //被判断数先除以2800个小素数提高效率
{
temp = BigNum(Primes[i]);
if (X == temp)
return 1;   //素数
if (X % temp == O) //合数
return 0;
}
m = *this - I;    //Y=被判断数-1
while (!(m.array[0] & 1))  //Y非奇数
{
r++;
m = m / E;
}      //求得r,Y，满足X-1=(2^r)*Y
for (int i = 1; i <= 5; ++i)  //由于一次判断不是素数的概率小等于1/4
{
int flag = 0;     //所以至少要进行5次判断以确保准确性
A.Random(X);                          //随机生成小于被判断数的数
while (A.Compare(T) == 2) A.Random(X);   //和上次避免产生相同的A
T = A;
Y = A.power_mod(m, X);                          // B=A^Y mod X
if ((O.Compare((Y - I) % X) == 2) || (O.Compare((Y + I) % X) == 2))
continue;                         //若B=1或X-1，则是素数
else
{
for (int j = 0; j < r; j++)
{
Y = (Y * Y) % X;                     //否则,B=b^2%X
if (O.Compare((Y + I) % X) == 2) //B=1,则是合数
{
flag = 1;
break;
}
}
}
if (flag)
continue;
else
return 0;
}
return 1;
}

/*产生 512 位的素数*/
void BigNum::GeneratePrime(void)
{
Random(0);   //确保符号为正
array[0] |= 1;     //确保是奇数以提高效率
while (!Rabin_Miller())
{
Random(0);
array[0] |= 1;
}
}

/*输出大数*/
void BigNum::print(void)
{
cout << hex;     //以十六进制打印
for (int i = 1; i <= length; ++i)
{
if (i % 8 == 1)
cout << endl;   //换行，8个数组元素一行
cout << setw(8) << array[length - i] << " ";
}
cout << dec << endl;
}

/*输出字符串，每一个array[i]存4个字符，每一次右移8位去出一个字符*/
void BigNum::printS(void)
{
for (int i = 0; i <= length; ++i)
for (int j = 3; j >= 0; --j)
{
char chr = char(array[i] >> (j * 8));   //右移8位取一个字符
if (chr) cout << chr;   //是字符输出
}
cout << endl;
}

/*求Y，使得X^A mod B=Y */
BigNum BigNum::power_mod(BigNum& A, BigNum& B)
{
BigNum X(1), N = (*this) % B;

for (int i = 0; i < A.length; i++)
{
for (int j = 0; j < 32; j++)  //转为2进制运算提高效率
{
if (A.array[i] & (1 << j))
X = (X * N) % B;
N = (N * N) % B;
}
}
return X;
}

/*扩展欧几里德算法，求X使得AX mod B=1*/
BigNum BigNum::ex_euclid(BigNum a, BigNum b)
{
BigNum X(1), U(0), O(0), A(a), B(b);   //A，B为了避免修改a，b的值

while (B != O)
{
BigNum Q(A / B), R(A % B), Temp;
Temp = Q * U;
Temp = X - Temp;
X = U;
U = Temp;
A = B;
B = R;
}
if (X.signal == 1) //负数时加上mod 的数b
{
X = X + b;
}
*this = X;   //传给当前大数
return *this;
}

BigNum Gcd(BigNum a, BigNum b);//求取最大公约数
BigNum Lcm(BigNum a, BigNum b);//求取最小公倍数
BigNum Lfunction(BigNum a);//求取L函数
BigNum n, I = 1, o = 0;

int main()
{
BigNum p, q, I(1), e(257), t, temp, d, a, b, c, O(0), middle, g, pri_key, g1, u;//b为密文，c为解密后结果
string A;
srand((unsigned)time(NULL));
cout << "输入要加密的字符串" << endl;
getline(cin, A);
cout << endl;
middle = BigNum(A);
cout << "生成明文：";
middle.print();
cout << endl;
p.GeneratePrime();   //产生素数
q.GeneratePrime();
while (p == q)   //判断两个素数不等
q.GeneratePrime();
temp = p - I;
t = q - I;
t = t * temp;
cout << "素数p为：";   //输出素数
p.print();
cout << endl;
cout << "素数q为：";
q.print();
cout << endl;
cout << "公钥n为";
n = p * q;
BigNum N = n * n;
n.print();
cout << endl;
pri_key = Lcm(p - I, q - I);
cout << "私钥pri_key为:";
pri_key.print();
cout << endl;
g.GeneratePrime();
cout << "公钥g为";
g.print();
cout << endl;
BigNum middle1, r;
r.GeneratePrime();
BigNum temp1 = g.power_mod(middle, N), temp2 = r.power_mod(n, N);
middle1 = temp1 * temp2;
b = middle1.power_mod(I, N);
cout << "生成密文如下:";
b.print();
cout << endl;
u.ex_euclid(Lfunction(g.power_mod(pri_key, N)), n);
c = Lfunction(b.power_mod(pri_key, N)) * u;
c = c.power_mod(I, n);//解密
cout << "解密后的结果为:" ;
c.print();
c.printS();
cout << endl;
system("pause");
return 0;
}

BigNum Gcd(BigNum a, BigNum b)
{
BigNum i;
do
{
i = a % b;
a = b;
b = i;
} while (b != o);
return a;
}

BigNum Lcm(BigNum a, BigNum b)
{
BigNum i;
i = Gcd(a, b);
i = a * b / i;
return i;
}

BigNum Lfunction(BigNum a)
{
BigNum i;
i = (a - I) / n;
return i;
}

代码运行截图


展开全文
• 基于整数多项式环的多对一全同态加密算法
• 陈智罡老师全同态加密算法深入解析：https://www.8btc.com/article/392931
• cryptdb中paillier同态加密算法的使用 1.paillier同态加密算法 1.1Paillier加密系统 Paillier加密系统，是1999年Paillier发明的概率公钥加密系统。基于复合剩余类的困难问题。该加密算法是一种同态加密，满足加法和...
• 2：同态加密算法原理3：标准化进展4： 主流同态加密算法原理4.1（1）乘法同态加密算法 1：什么是同态加密？ 同态加密（Homomorphic Encryption, HE） 是指满足密文同态运算性质的加密算法，即数据经过同态加密之后，...
• 1.1.Paillier加法同态加密算法 Paillier加密算法[1]是1999年Paillier发明的基于复合剩余类的困难问题的加法同态加密算法。 （1）秘钥生成 随机选择两个大质数p和q满足gcd(pq,(p−1)(q−1))=1gcd(pq, (p−1)(q−1))=...
• 本文主要讲述完全同态加密算法。 1. 是什么鬼？ 同态加密是一种对称加密算法，由Craig Gentry发明提出。其同态加密方案包括4个算法，即密钥生成算法、加密算法、解密算法和额外的评估算法。全同态加密包括两种基本...
• 针对改进云计算中服务器端数据的安全性和计算效率，结合全同态加密体制原理，根据云计算的特点提出了一种基于单同态的RSA和Bresson算法的混合全同态算法。该算法在保证数据传输存储安全的基础上，能够实现在云服务器...
• ## java实现同态加密算法

千次阅读 多人点赞 2020-12-29 17:16:57
什么是同态加密同态加密是上世纪七十年代就被提出的一个开放问题，旨在不暴露数据的情况下完成对数据的处理，关注的是数据处理安全。 想象一下这样一个场景，作为一名满怀理想的楼二代，你每天过着枯燥乏味的收...
• BGN同态加密算法： BGN是一种同态加密方案，是Bonelh等人在2005提出的一种具有全同态性质的加密方案。和传统的仅能支持单同态的elgamal和paillier加密方案不一样，BGN能够同时支持加同态和一次乘同态运算。 由于...
• BGN是一种同态加密方案，是Boned D等人在2005提出的一种具有全同态性质的加密方案。和传统的仅能支持单同态的elgamal和paillier加密方案不一样，BGN能够同时支持加同态和一次乘同态运算。 BGN的实现我们主要使用JAVA...
• 同态加密的研究现状进行了综述,介绍了同态加密在云计算机密性保护及其他方面的应用,重点介绍了各种代数部分同态加密方案和电路全同态加密方案的优缺点.对同态加密未来的研究问题进行了分析,同时简单介绍了云安全中...
• ## 同态加密算法简述

万次阅读 多人点赞 2018-01-21 18:04:00
同态加密如果我们有一个加密函数 f , 把明文A变成密文A’, 把明文B变成密文B’，也就是说 f(A) = A’ ， f(B) = B’ 。另外我们还有一个解密函数 f−1f^{-1} 能够将 f 加密后的密文解密成加密前的明文。对于一般的...
• 背景 Y随着互联网的迅速普及,云计算,语义网,物联网,智 慧地球等概念或服务的推出,对网络信息安全提出了更 高的要求对于这些应用,我们可以看到,它都有一个 特点,就是信息在网络中传送,在远程处理,或与远程 协作处理,...
• 高安全性同态加密算法I was going to write at length about the issues I see in neumorphism and why this trend should be avoided. I know any attempt to guide my most impressionable colleagues away from ...
• 基于同态加密算法设计了安全的乘法协议、单个密钥加密下的完全平方式协议和联合公钥加密下的完全平方式协议，基于这三个基础计算协议设计了欧氏距离的外包计算协议。安全性分析表明该协议足够安全，效率分析显示该...
• Paillier，同态加密算法。java版。懂得都懂。找了很久，才找到下面的东西。 直接上链接。 http://www.csee.umbc.edu/~kunliu1/research/Paillier.html 稍微修改一下，代码如下。 /** * This program is free...
• ## 同态加密算法-总结

千次阅读 2020-06-14 14:36:46
文章目录1、定义2、同态分类3、应用4、意义 1、定义 一般的加密方案关注的都是数据存储安全。即，我要给其他人发个加密的东西，或者要在计算机或者其他服务器上存一个东西，我要对数据进行加密后在发送或者...同态加密
• 高安全性同态加密算法I was looking for the latest UI and UX design trends in dribble, and I heard of a concept often called neumorphism. 我一直在寻找运球的最新UI和UX设计趋势，并且听说过一个通常称为...

...