济南住建局官方网站,做网站需要审核资质吗,番禺网站开发企业,企业代理注册公司1. 背景介绍 本篇主要关注中国剩余定理的原理以及在paillier同态加密系统中的应用。在很多工作中#xff0c;都可以看到中国剩余定理的影子#xff0c;特别是同态加密提升计算效率的优化工作中#xff0c;将paillier与中国剩余定理进行结合#xff0c;能够实现在加密状态下…1. 背景介绍 本篇主要关注中国剩余定理的原理以及在paillier同态加密系统中的应用。在很多工作中都可以看到中国剩余定理的影子特别是同态加密提升计算效率的优化工作中将paillier与中国剩余定理进行结合能够实现在加密状态下进行高效计算。
2. Paillier加密系统 【123】描述了paillier加密系统的原理。这里做简单的描述。Paillier加密算法是一种同态加密算法支持加法同态运算。该算法的安全性基于大整数的分解困难问题具体的加密和解密过程涉及模数 上的运算计算复杂度较高。
2.1 Paillier密钥生成
选择两个大质数 p 和 q计算 。公钥为 N 和 g通常选择 g N 1。私钥为 和 其中 即 p-1 和 q-1 的最小公倍数。其中 。
2.2 加密和解密
加密给定明文 m选择随机数 r计算密文 。解密给定密文 c解密过程为这里的模 运算会涉及非常大的数计算较为耗时。
3. 中国剩余定理CRT
3.1 算法描述 中国剩余定理Chinese Remainder Theorem, CRT【45】是数论中的一个经典定理用来解决模数互素时同余方程组的求解问题。它最早起源于中国古代数学家孙子在《孙子算经》中的研究。 设 是两两互素的整数也就是说对于有 。给定同余方程组 其中 是给定的整数则该方程组有唯一解 x 模 并且解的形式为 定理的意义 解的存在性如果模数 互素则方程组总有解。解的唯一性在模 意义下解是唯一的。 解法步骤
计算总模数计算模数的乘积 。计算每个模的辅助量对于每个 i计算 即其他模数的乘积。计算模逆元对于每个 i找到 模 的逆元 即满足 的整数 。求解 x解的形式为 其中 是同余方程组中的常数项 是步骤 2 中的值 是步骤 3 中的模逆元。
此外也关注到【6】对于中国剩余定理的解释比较清晰这里也贴一下以便参考学习。 3.2 模 n 同余概念 模 n 同余是数论中的一个概念用来表示两个整数在被同一个整数 n 除时得到相同的余数。具体来说模 n 同余是指两个整数 a 和 b如果 a 和 b 被 n 除后余数相同那么我们说 a 和 b 在模 n 意义下同余记作 这表示 a - b 能被 n 整除即存在某个整数 k 使得 其中 a 和 b 是两个整数。 n 是模数或称模量是一个正整数。 表示当 a 和 b 都被 n 除后余数相同或者说 a - b 是 n 的倍数。
3.3 中国剩余定理应用问题说明 中国剩余定理的原问题如下 有物不知其数三三数之剩二五五数之剩三七七数之剩二。问物几何 问题的意思是找一个数 x满足以下三个同余条件 我们要解这个系统找到 x 满足所有条件。 解法步骤 从第一个和第二个条件开始 设 代入 即 我们需要解这个同余方程。找到 即 3 在模 5 下的逆元。通过尝试 所以 。即 代入 考虑第三个条件 现在有 代入 即 由于 所以 考虑 所以这个方程化简为 即 。代入 得出最终结果 所以满足条件的数 x 可以表示为 其中 n 是任意整数。因此最小的正整数解是 x 23。 所以这个物的数是 23。 4. Paillier引入中国剩余定理
4.1 思路介绍 中国剩余定理与Paillier加密算法结合可以有效提升计算效率尤其是在大数模运算的场景中。通过利用中国剩余定理的性质将涉及大整数的计算拆分为两个较小模数空间中的并行计算从而加快整体的运算速度。这种结合方式在Paillier加密算法中的典型应用是加速解密过程。 具体地中国剩余定理用于将大整数的计算分解为在较小整数模数下的并行计算。对于给定的两个模数 p 和 q可以将模 下的计算转化为模 p 和模 q 下的两个独立计算。 设 对于任何整数 x有 通过在较小模数空间中分别计算 和 可以加快运算速度。 Paillier算法中的解密操作主要依赖于模 的运算而 是一个非常大的数。通过中国剩余定理可以将这些大模数运算分解为在较小模数 和 下的并行计算从而加速解密过程。
4.2 处理步骤 分解模数空间 利用中国剩余定理将模 下的运算分解为模 和模 的运算。 并行计算 在解密过程中密文 c 的解密需要计算 。通过中国剩余定理可以将这一操作分解为 其中 。 重构结果 利用中国剩余定理的逆过程将模 和模 下的结果 和 通过CRT重构为最终的明文 这一步通过快速计算结合模 p 和 q 的结果得到最终的解密结果。在原始论文【2】中其实也列出了相应的说明 通过将模 下的计算分解为较小的模 和模 下的计算可以显著减少大整数运算的复杂度。由于 和 远小于 N^2解密速度可以得到明显提升。
4.3 推理依赖的定理 这里根据哥大的材料【7】列出paillier系统相关的定理有兴趣可以看下定理的证明过程。
5. 参考材料
【1】A Restrained Paillier Cryptosystemand Its Applications for Access Control of Common Secret
【2】Public-Key Cryptosystems Based on Composite Degree Residuosity Classes
【3】Paillier同态加密算法
【4】中国剩余定理
【5】The Chinese Remainder Theorem
【6】密码学-05-中国剩余定理
【7】Facts Related to Paillier Encryption
