(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 20221097425 6.7 (22)申请日 2022.08.15 (71)申请人 梁庆生 地址 523000 广东省东莞 市莞城区西正路 15号4楼 (72)发明人 梁庆生　 (74)专利代理 机构 北京卓恒知识产权代理事务 所(特殊普通 合伙) 11394 专利代理师 袁定田 (51)Int.Cl. H04L 9/30(2006.01) H04L 9/32(2006.01) H04L 9/06(2006.01) H04L 9/40(2022.01) (54)发明名称 一种可抵御量子计算机攻击的非对称加密 及签名方法 (57)摘要 本发明公开了一种可抵御量子计算机攻击 的非对称加密及签名方法， 本发 明步骤包括签名 密钥的生成、 明文的签名、 明文的验签、 加密密钥 的产生、 明文的加密和密文的解密， 签名原理是 构造一个具有陷井的高次剩余方程一， 使用私钥 对方程一求解得到签名， 使用公钥验证方程一是 否成立来验证签名； 加密原理是构造一个具有陷 井的高次剩余方程二， 使用公钥对 方程二进行计 算求得密文， 使用私钥求方程二关于密文的解获 得明文。 该签名及加密算法能够 有效地对抗量子 计算机的Shor算 法及Grover算 法的攻击， 同时速 度快， 效率高， 位数少， 提高了加密数据的安全性 及签名的真实性。 权利要求书4页 说明书8页 附图1页 CN 115333740 A 2022.11.11 CN 115333740 A 1.一种可抵御量子计算机攻击的非对称加密 及签名方法， 其特 征在于： 包括如下步骤： S1、 签名密钥的生成， 基于高次剩余方程的方程一xh≡t2(modN)， 其中t为明文， x为要求 的签名数据， h为素数， 随机生成i个素数p1， p2， p3...， pi， 称为K1集合， 再根据p1， p2， p3...， pi‑1求符合陷井条件的条件一及条件二的素数pi， 重复上述步骤直至生 成j个集合， 即K1、 K2、 K3…Kj， 最后将K1至Kj集合中的所有元素相乘后求得N， 将N及h作为公钥， 可以公开， K1至Kj集 合作为私钥K， 不公开； S2、 明文的签名， 设有一明文t， 且gcd(t， N)＝＝1， 已知公钥N及h， 利用私钥K1、 K2、 K3… Kj， 根据高次剩余方程： xh≡t2(modN)， 求高次剩余方程的解x0， x0即为签名后的数据x0； S3、 明文的验签， 要对明文t进行验签， 只需要验证签名后的数据x0是否为高次剩余方程 的解即可； S4、 加密密钥的产生， 根据同余定理将方程二xh≡d(modN)可转化为如下第一方程和第 二方程， 第一方程为yh≡d3(mod N)， 第二方程为x3≡y(modN)， 其中d为明文t加密后的密文， y为加密数据， 随机生成i个素数p1， p2， p3...， pi， 称为K1集合， 再根据p1， p2， p3...， pi‑1求符合 陷井条件的条件三、 条件四及条件五的素数pi， 重复上述步骤直至生成j个集合， 即K1、 K2、 K3…Kj， 最后将K1至Kj集合中的所有元素相乘后求得N， 判断 是否成 立； 若成立， 则附加数据A为1， 若不成立， 则附加数据A为3， 最后将N乘以A， 即： N＝N＊A， 将N 及h作为公钥， 可以公开， K1至Kj集合以及附加数A作为私钥K， 不公开； S5、 明文的加密， 设有一明文t， 且gcd(t， N)＝＝1， 根据 方程d≡th(mod N)计算出d， d即 为明文t加密后的密文； S6、 密文的解密， 先根据陷井条件的条件三 及条四件N＝A*K1*K2*K3* ...求第一方程yh≡d3(mod N)的解y， 再根据条件五 求第二方程x3≡y(modN)的解x， 第二方程 的解x0即为加密前的明文 t。 2.根据权利要求1所述的一种可抵御量子计算机攻击的非对称加密及签名方法， 其特 征在于： 步骤S1及S4所述陷井条件如下： 条件一为： 条件二为： N＝K1*K2*K3*... 条件三为： 条件四为： N ＝A*K1*K2*K3*... 及有条件五： 3.根据权利要求1所述的一种可抵御量子计算机攻击的非对称加密及签名方法， 其特 征在于： 步骤S1及S4所述方程一和方程二也可以是xH≡t(mod  3p)， 陷井条件为是 及H＝h1*h2。 4.根据权利要求1所述的一种可抵御量子计算机攻击的非对称加密及签名方法， 其特 征在于： 所述签名密钥的生成具体步骤如下： A1、 先随机生成一素 数集合K1， 该集合中共有25 6个素数元素， 分别为： p1， p2， p3...， p256； A2、 K1集合中的每一个元 素pn， 都符合 A3、 K1集合中的第一个元 素p1为大的素 数， p2， p3...， p256为小的素 数；权　利　要　求　书 1/4 页 2 CN 115333740 A 2A4、 然后， 再根据p1， p2， p3...， p255求一符合条件一的素 数p256； A5、 由 性质可知： 及 故 并立即推出方程二： (p1‑1)* (p2‑1)*...*(p256‑1)≡‑2(mod h)； A6、 由于方程二为一元一次剩余方程， 有解且有无数解， 因而可通过有限次的测试， 获 得符合条件一的一素 数解p256； A7、 接着， 再重A1至A6的步骤， 生成K2集合； A8、 至此， 一共生成两个这样的集 合， 即K1， K2； A9、 将K1至K2集合中的所有元 素相乘后求得N； A10、 将N及h作为公钥， 可以公开， K1至K2集合作为私钥K， 为私有不公开。 5.根据权利要求1所述的一种可抵御量子计算机攻击的非对称加密及签名方法， 其特 征在于： 步骤2中所述明文的签名的具体步骤如下： B1、 对要进行签名的数据m进行SM 3哈希运算后， 得出哈希后的数据t； B2、 若gcd(t， N)≠1， 则令t＝t+1； B3、 重复B2， 直至gcd(t， N)＝1为止； B4、 接着， 根据方程 一： xh≡t2(modN)， 求方程 一的解x0， x0即为签名后的数据x0； B5、 由于已知有条件二： N ＝K1*K2， 由方程一可得如下方程组一： x1h≡t2(mod K1) x2h≡t2(mod K2)； B6、 先求方程组一中的x1h≡t2(mod K1)的解x′1； B7、 根据条件一有 根据费马小定理及同余理论可推出： B8、 接着再分别求方程组一中的： x2h≡t2(mod K2)的解x′2； B9、 将x′1， x′2， 称之为集合X′； B10、 若K1*x′1＝1mod K1， K2*x′2＝1mod K2， 则可根据孙子定 理及集合X ′， 求得方程组一 的解x0’为： x0‘≡(x′1*K′1*K1+x′2*K′2*K2)(mod N)， 方程组一的解x0’即方程一的解， 满足x0h ≡t2(modN)， 亦即为签名后的数据。 6.根据权利要求1所述的一种可抵御量子计算机攻击的非对称加密及签名方法， 其特 征在干： 步骤S3中所述明文的验签具体步骤如下： C1、 对要进行签名的数据m进行SM 3哈希运算后， 得出哈希后的数据t； C2、 若gcd(t， N)≠1， 则令t＝t+1； C3、 重复C2， 直至gcd(t， N)＝1为止； C4、 验证签名数据x0是否为方程一的解即可； 即x0h≡t2(mod N)是否成立， 若成立， 则为 有效签名， 否则为无效签名。 7.根据权利要求2所述的一种可抵御量子计算机攻击的非对称加密及签名方法， 其特 征在于： 步骤S4中所述加密 密钥的产生具体步骤如下： D1、 先随机生成一素 数集合K1， 该集合中共有25 6个素数元素， 分别为： p1， p2， p3...， p256； D2、 K1集合中的每一个元 素pn， 都符合 且 权　利　要　求　书 2/4 页 3 CN 115333740 A 3