[go: up one dir, main page]

CN111740821A - 建立共享密钥的方法及装置 - Google Patents

建立共享密钥的方法及装置 Download PDF

Info

Publication number
CN111740821A
CN111740821A CN202010371284.0A CN202010371284A CN111740821A CN 111740821 A CN111740821 A CN 111740821A CN 202010371284 A CN202010371284 A CN 202010371284A CN 111740821 A CN111740821 A CN 111740821A
Authority
CN
China
Prior art keywords
subgroup
key
establishing
private key
braid group
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Granted
Application number
CN202010371284.0A
Other languages
English (en)
Other versions
CN111740821B (zh
Inventor
王晓峰
林汉玲
凌一品
王威鉴
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Shenzhen University
Original Assignee
Shenzhen University
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Shenzhen University filed Critical Shenzhen University
Priority to CN202010371284.0A priority Critical patent/CN111740821B/zh
Publication of CN111740821A publication Critical patent/CN111740821A/zh
Application granted granted Critical
Publication of CN111740821B publication Critical patent/CN111740821B/zh
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/08—Key distribution or management, e.g. generation, sharing or updating, of cryptographic keys or passwords
    • H04L9/0816—Key establishment, i.e. cryptographic processes or cryptographic protocols whereby a shared secret becomes available to two or more parties, for subsequent use
    • H04L9/085—Secret sharing or secret splitting, e.g. threshold schemes
    • Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
    • Y04—INFORMATION OR COMMUNICATION TECHNOLOGIES HAVING AN IMPACT ON OTHER TECHNOLOGY AREAS
    • Y04S—SYSTEMS INTEGRATING TECHNOLOGIES RELATED TO POWER NETWORK OPERATION, COMMUNICATION OR INFORMATION TECHNOLOGIES FOR IMPROVING THE ELECTRICAL POWER GENERATION, TRANSMISSION, DISTRIBUTION, MANAGEMENT OR USAGE, i.e. SMART GRIDS
    • Y04S40/00—Systems for electrical power generation, transmission, distribution or end-user application management characterised by the use of communication or information technologies, or communication or information technology specific aspects supporting them
    • Y04S40/20—Information technology specific aspects, e.g. CAD, simulation, modelling, system security

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Security & Cryptography (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Complex Calculations (AREA)
  • Lock And Its Accessories (AREA)

Abstract

本申请适用于信息安全技术领域，提供了一种建立共享密钥方法及装置，可以解决基于现有公钥密码的安全性存在隐患的问题。一种建立共享密钥方法，包括：第一设备确定指数为n的辫群Bn为公钥；第一设备选取辫群Bn的多个元素生成的一个子群P，并从子群P中选取一个元素x作为第一私钥；第一设备接收第二设备发送的{y‑1σ1y,y‑1σ2y,...,y‑1σn‑1y}；第一设备将第一私钥与公钥的每个元素计算得到的{x‑1σ1x,x‑1σ2x,...,x‑1σn‑1x}发送给第二设备，以使得第二设备将第二私钥中的所有σk替换为x‑1σkx，得到fy(x‑1σ1x,x‑1σ2x,...,x‑1σn‑1x)＝x‑1yx，并计算得到共享密钥x‑1y‑1xy；将第一设备的第一私钥中的所有σk替换为y‑1σky，得到fx(y‑1σ1y,y‑1σ2y,...,y‑1σn‑1y)＝y‑1xy，并计算得到共享密钥为x‑1y‑1xy。

Description

建立共享密钥的方法及装置
技术领域
本申请属于信息安全技术领域，尤其涉及一种建立共享密钥的方法及装置。
背景技术
在经典公钥密码算法中，作为安全保障的实际计算困难问题，随着计算机性能的提高其难解性将大大降低。特别地，量子计算系统基于Shor于1997年提出的著名的Shor量子算法将分别在多项式时间内进行大整数的因数分解和离散对数的计算，而Google和IBM已分别宣称其设计的量子计算系统已经实现或正在实现。这意味着基于RSA,ECC,ElGamal等算法建立的公钥密码协议将不再安全。
另一方面，针对Ansheld等人提出的基于辫群的元素的共轭问题建立密钥交换协议,人们陆续发现了诸如基于长度的攻击、线性表示攻击、Super-Summit-set攻击等攻击方案。从而,对应的公钥密码体制也存在着安全隐患。
发明内容
本申请实施例提供了一种建立共享密钥的方法及装置，可以解决基于现有公钥密码的安全性存在隐患的问题，建立一个能抗击各种攻击的共享密钥的方法。
第一方面，本申请实施例提供了一种建立共享密钥的方法，包括：第一设备确定指数为n的辫群Bn为公钥；其中，Bn＝<σ1,σ2,…,σn-1|σiσj＝σjσi,|i-j|≥2,σiσi+1σi＝σi+1σiσi+1,1≤i≤n-2>；所述辫群Bn中的每个元素均以集合{σ1,σ2,…,σn-1}上代表该元素的字表示，且所述字具有唯一性的正规形式，n≥6，n为整数；所述第一设备选取辫群Bn的多个元素生成的一个子群P，并从子群P中选取一个元素x作为第一私钥，其中，对x的限定为x＝fx(σ1,σ2,…,σn-1)；所述第一设备接收所述第二设备发送的{y-1σ1y,y-1σ2y,...,y-1σn-1y}；其中，所述第二设备为与所述第一设备建立共享密钥的设备，y-1σky是第二设备选取辫群Bn的多个元素生成的一个子群Q，并从子群Q中选取一个元素y作为第二私钥，根据第二私钥与所述公钥中的每个元素计算得到的；其中，对y的限定为y＝fy(σ1,σ2,…,σn-1)；k＝1,2,…,n-1；所述第一设备将所述第一私钥x与所述公钥的每个元素计算得到的{x-1σ1x,x-1σ2x,...,x-1σn- 1x}发送给第二设备，以使得第二设备将所述第二私钥y中的所有σk替换为x-1σkx，得到fy(x-1σ1x,x-1σ2x,...,x-1σn-1x)＝x-1yx，并计算得到共享密钥x-1y-1xy；将所述第一设备的第一私钥x中的所有σk替换为y-1σky，得到fx(y-1σ1y,y-1σ2y,...,y-1σn-1y)＝y-1xy，并计算得到共享密钥为x-1y-1xy。
本申请实施例提供了一种建立共享密钥的方法，基于第一设备和第二设备确定指数为n的辫群Bn作为双方公钥；双方分别从辫群Bn中选取一个子群，以及将子群中的一个元素作为自己的私钥；再将各自的私钥与公钥的每一元素进行共轭计算；然后，双方分别将各自的共轭结果发送给对方，再根据共轭结果计算得到共享密钥。由于引入的辫群Bn、子群的成员问题是不可解的，因此，所建立的共享密钥的的方法的安全性在理论上得到充分证明，可以量子计算攻击等各种攻击。
可选地，所述第一设备选取辫群Bn的多个元素生成的一个子群P，包括：所述辫群Bn含有与两个秩为2的自由群的直积同构的子群Lu：Lu＝<σu 2,σu+1 2,σu+3 2,σu+4 2>；u＝1,2,...,n-5；根据所述子群Lu的元素，生成子群Mu：Mu＝<σu 2σu+3 2,σu+1 2σu+4 2,Suv,Tuv>；v＝1,2,...,27；选取一个所述子群Mu作为所述子群P。
可选地，当u＝1,2,...,n-5时，27个Suv分别为：
Figure BDA0002478388390000031
Figure BDA0002478388390000032
Figure BDA0002478388390000033
Figure BDA0002478388390000034
Figure BDA0002478388390000035
Figure BDA0002478388390000036
Figure BDA0002478388390000037
Figure BDA0002478388390000038
Figure BDA0002478388390000039
Figure BDA00024783883900000310
Figure BDA00024783883900000311
Figure BDA00024783883900000312
Figure BDA00024783883900000313
Figure BDA00024783883900000314
Figure BDA0002478388390000041
Figure BDA0002478388390000042
Figure BDA0002478388390000043
Figure BDA0002478388390000044
Figure BDA0002478388390000045
Figure BDA0002478388390000046
Figure BDA0002478388390000047
Figure BDA0002478388390000048
Figure BDA0002478388390000049
Figure BDA00024783883900000410
Figure BDA0002478388390000051
Figure BDA0002478388390000052
Figure BDA0002478388390000053
Figure BDA0002478388390000054
Figure BDA0002478388390000055
可选地，将所述27个Suv中的σu替换为σu+3，σu+1替换为σu+4得到对应的27个Tuv。
可选地，所述子群P和所述子群Q均为具有子群成员不可解的Mihailova子群。
第二方面，本申请实施例提供了一种建立共享密钥的装置，包括：应用于第一设备，所述建立共享密钥的装置包括处理单元和收发单元；所述处理单元，用于确定指数为n的辫群Bn为公钥；其中，Bn＝<σ1,σ2,…,σn-1|σiσj＝σjσi,|i-j|≥2,σiσi+1σi＝σi+1σiσi+1,1≤i≤n-2>；所述辫群Bn中的每个元素均以集合{σ1,σ2,…,σn-1}上代表该元素的字表示，且所述字具有唯一性的正规形式，n≥6，n为整数；还用于选取辫群Bn的多个元素生成的一个子群P，并从子群P中选取一个元素x作为第一私钥，其中，对x的限定为x＝fx(σ1,σ2,…,σn-1)；所述收发单元，用于接收所述第二设备发送的{y-1σ1y,y-1σ2y,...,y-1σn-1y}；其中，所述第二设备为与所述第一设备建立共享密钥的设备，y-1σky是第二设备选取辫群Bn的多个元素生成的一个子群Q，并从子群Q中选取一个元素y作为第二私钥，根据第二私钥与所述公钥中的每个元素计算得到的；其中，对y的限定为y＝fy(σ1,σ2,…,σn-1)；k＝1,2,…,n-1；还用于将所述第一私钥x与所述公钥的每个元素计算得到的{x-1σ1x,x-1σ2x,...,x-1σn-1x}发送给第二设备，以使得第二设备将所述第二私钥y中的所有σk替换为x-1σkx，得到fy(x-1σ1x,x-1σ2x,...,x-1σn-1x)＝x-1yx，并计算得到共享密钥x-1y-1xy；所述处理单元，还用于将所述第一设备的第一私钥x中的所有σk替换为y-1σky，得到fx(y-1σ1y,y-1σ2y,...,y-1σn-1y)＝y-1xy，并计算得到共享密钥为x-1y-1xy。
可选地，所述处理单元，用于选取辫群Bn的多个元素生成的一个子群P，包括：所述辫群Bn含有与两个秩为2的自由群的直积同构的子群Lu：Lu＝<σu 2,σu+1 2,σu+3 2,σu+4 2>；u＝1,2,...,n-5；所述处理单元，用于根据所述子群Lu的元素，生成子群Mu：Mu＝<σu 2σu+3 2,σu+1 2σu+4 2,Suv,Tuv>；v＝1,2,...,27；还用于选取一个所述子群Mu作为所述子群P。
可选地，当u＝1,2,...,n-5时，27个Suv分别为：
Figure BDA0002478388390000071
Figure BDA0002478388390000072
Figure BDA0002478388390000073
Figure BDA0002478388390000074
Figure BDA0002478388390000075
Figure BDA0002478388390000076
Figure BDA0002478388390000077
Figure BDA0002478388390000078
Figure BDA0002478388390000079
Figure BDA00024783883900000710
Figure BDA00024783883900000711
Figure BDA00024783883900000712
Figure BDA00024783883900000713
Figure BDA00024783883900000714
Figure BDA0002478388390000081
Figure BDA0002478388390000082
Figure BDA0002478388390000083
Figure BDA0002478388390000084
Figure BDA0002478388390000085
Figure BDA0002478388390000086
Figure BDA0002478388390000087
Figure BDA0002478388390000088
Figure BDA0002478388390000089
Figure BDA00024783883900000810
Figure BDA0002478388390000091
Figure BDA0002478388390000092
Figure BDA0002478388390000093
Figure BDA0002478388390000094
Figure BDA0002478388390000095
将所述27个Suv中的σu替换为σu+3，σu+1替换为σu+4得到对应的27个Tuv。
第三方面，本申请实施例提供了一种计算机设备，包括：存储器、处理器以及存储在所述存储器中并可在所述处理器上运行的计算机程序，所述处理器执行所述计算机程序时实现如上所述的建立共享密钥的方法。
第四方面，本申请实施例提供了一种计算机可读存储介质，所述计算机可读存储介质存储有计算机程序，所述计算机程序被处理器执行时实现如上所述的建立共享密钥的方法。
第五方面，本申请实施例提供了一种计算机程序产品，当计算机程序产品在计算机设备上运行时，使得计算机设备执行上述第一方面中任一项所述的建立共享密钥的方法。
可以理解的是，上述第二方面至第五方面的有益效果可以参见上述第一方面中的相关描述，在此不再赘述。
附图说明
为了更清楚地说明本申请实施例中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本申请的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动性的前提下，还可以根据这些附图获得其他的附图。
图1是本申请一实施例提供的应用场景图；
图2是本申请一实施例提供的建立共享密钥的方法的交互示意图；
图3是本申请一实施例提供的建立共享密钥的装置的示意图；
图4是本申请一实施例提供的计算机设备的结构示意图。
具体实施方式
为了使本申请的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本申请进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本申请，并不用于限定本申请。
本申请的实施例提供的建立共享密钥的方法，可以应用于计算机设备，如图1所示，在计算机设备1和计算机设备2之间建立共享密钥。
计算机设备1包括存储器、处理器以及存储在存储器中并可在处理器上运行的计算机程序，处理器执行计算机程序时实现如本申请所述的建立共享密钥的方法。
其中，存储器在一些实施例中可以是计算机设备1的内部存储单元，例如计算机设备1的硬盘或内存。存储器在另一些实施例中也可以是计算机设备1的外部存储设备，例如计算机设备1上配备的插接式硬盘，智能存储卡(Smart Media Card,SMC)，安全数字(Secure Digital,SD)卡，闪存卡(Flash Card)等。存储器还可以既包括计算机设备1的内部存储单元也包括外部存储设备。存储器用于存储操作系统、应用程序、引导装载程序(Boot Loader)、数据以及其他程序等，例如计算机程序的程序代码等。存储器还可以用于暂时地存储已经输出或者将要输出的数据。
处理器可以是中央处理单元(Central Processing Unit，CPU)，该处理器还可以是其他通用处理器、数字信号处理器(Digital Signal Processor，DSP)、专用集成电路(Application Specific Integrated Circuit，ASIC)、现成可编程门阵列(Field-Programmable Gate Array，FPGA)或者其他可编程逻辑器件、分立门或者晶体管逻辑器件、分立硬件组件等。通用处理器可以是微处理器或者该处理器也可以是任何常规的处理器等。
可以理解的是，本申请实施例示意的结构并不构成对计算机设备1的具体限定，在另一些实施例中，计算机设备1可以包括比图示更多或更少的部件，或者组合某些部件，或者拆分某些部件，或者不同的部件布置。图示的部件可以以硬件，软件或软件和硬件的组合实现。计算机设备2与计算机设备1结构可以相同，在此不再赘述。
在现有技术中，一方面，由于量子计算系统已经实现或正在实现，使得基基于RSA,ECC,ElGamal等算法建立的公钥密码协议将不再安全。另一方面，针对Ansheld等人提出的基于辫群的元素的共轭问题建立密钥交换协议,人们陆续也发现了诸如基于长度的攻击、线性表示攻击、Super-Summit-set攻击等攻击方案。从而,对应的公钥密码体制也存在着安全隐患。
为此，本申请提供了一种建立共享密钥的方法，由于引入的子群的成员问题是不可解的，因此，所建立的共享密钥的的方法的安全性在理论上得到充分证明，可以量子计算攻击等各种攻击。
下面结合本申请实施例中的附图对本申请实施例进行描述。
本申请提供一种建立共享密钥的方法，可以应用于上述的图1中的计算机设备1或者计算机设备2。其中，计算机设备1执行该方法时作为第一设备，而计算机设备2作为第二设备；或者，计算机设备2执行该方法时作为第一设备，而计算机设备1作为第二设备。
如图2所示，该方法包括：
S21、第一设备确定指数为n的辫群Bn为公钥。
其中，Bn＝<σ1,σ2,…,σn-1|σiσj＝σjσi,|i-j|≥2,σiσi+1σi＝σi+1σiσi+1,1≤i≤n-2>；辫群Bn中的每个元素均以集合{σ1,σ2,…,σn-1}上代表该元素的字表示，且字具有唯一性的正规形式(normal form)，n≥6，n为整数。
需要说明的是，基于正规形式的群的乘积运算和求逆运算时能行可计算的。
S22、第二设备确定指数为n的辫群Bn为公钥。
其中，第二设备为与第一设备建立共享密钥的设备，第二设备与第一设备确定的公钥相同。
S23、第一设备选取辫群Bn的多个元素生成的一个子群P，并从子群P中选取一个元素x作为第一私钥。其中，对x的限定为x＝fx(σ1,σ2,…,σn-1)。
其中，x是σ1,σ2,…,σn-1的方幂(整数指数)的乘积，即可表示为x＝fx(σ1,σ2,…,σn-1)
可选地，第一设备选取辫群Bn的多个元素生成的一个子群P，包括：
辫群Bn含有与两个与F2×F2同构的子群Lu，即，由σu 2,σu+1 2,σu+3 2,σu+4 2生成的两个秩为2的自由群的直积同构的子群Lu：Lu＝<σu 2,σu+1 2,σu+3 2,σu+4 2>；u＝1,2,...,n-5。
根据子群Lu的元素，生成子群Mu：Mu＝<σu 2σu+3 2,σu+1 2σu+4 2,Suv,Tuv>；v＝1,2,...,27。
第一设备选取其中一个子群Mu作为子群P。
其中，当u＝1,2,...,n-5时，27个Suv分别为：
Figure BDA0002478388390000131
Figure BDA0002478388390000132
Figure BDA0002478388390000133
Figure BDA0002478388390000134
Figure BDA0002478388390000135
Figure BDA0002478388390000136
Figure BDA0002478388390000137
Figure BDA0002478388390000138
Figure BDA0002478388390000139
Figure BDA00024783883900001310
Figure BDA00024783883900001311
Figure BDA00024783883900001312
Figure BDA00024783883900001313
Figure BDA00024783883900001314
Figure BDA0002478388390000141
Figure BDA0002478388390000142
Figure BDA0002478388390000143
Figure BDA0002478388390000144
Figure BDA0002478388390000145
Figure BDA0002478388390000146
Figure BDA0002478388390000147
Figure BDA0002478388390000148
Figure BDA0002478388390000149
Figure BDA00024783883900001410
Figure BDA0002478388390000151
Figure BDA0002478388390000152
Figure BDA0002478388390000153
Figure BDA0002478388390000154
Figure BDA0002478388390000155
将27个Suv中的σu替换为σu+3，σu+1替换为σu+4得到对应的27个Tuv。
需要说明的是，第二设备选取辫群Bn的多个元素生成的一个子群Q的方法与第一设备选取辫群Bn的多个元素生成的一个子群P的方法相同，在此不再赘述。
基于此，子群P和子群Q可以相同，也可以不同。
S24、第二设备选取辫群Bn的多个元素生成的一个子群Q，并从子群Q中选取一个元素y作为第二私钥。其中，对y的限定为y＝fy(σ1,σ2,…,σn-1)。
其中，y是σ1,σ2,…,σn-1的方幂(整数指数)的乘积，即可表示为y＝fy(σ1,σ2,…,σn-1)。
还需要说明的是，辫群Bn的指数n≥6。
应理解的，当n＝6时，u的取值范围为1，则辫群Bn含有与两个的两个秩为2的自由群的直积同构的子群为L1：L1＝<σ1 2,σ2 2,σ4 2,σ5 2>，即，两个子群是相同的。再根据子群L1的元素，可以生成子群M1：M1＝<σ1 2σ4 2,,σ2 2σ5 2,S1v,T1v>；v＝1,2,...,27。此时，由于只生成了子群M1，所以第一设备可以选取子群M1作为子群P，同理，第二设备也可以选取子群M1作为子群Q。
应理解的，当n＝7时，u的取值范围为1或2，则辫群Bn含有与两个的两个秩为2的自由群的直积同构的子群，分别为L1和L2，其中，L1＝<σ1 2,σ2 2,σ4 2,σ5 2>，L2＝<σ2 2,σ3 2,σ5 2,σ6 2>；再根据子群L1元素，可以生成子群M1：M1＝<σ1 2σ4 2,σ2 2σ5 2,S1v,T1v>；根据子群L2元素，可以生成子群M2：M2＝<σ2 2σ5 2,σ3 2σ6 2,S2v,T2v>。此时，由于生成了两个子群M1和M2，所以第一设备可以选取子群M1或子群M2作为子群P。同理，第二设备也可以选取子群M1或子群M2作为子群Q。
应理解的，当n＝8时，u的取值范围为1、2或3，则辫群Bn含有与两个多个秩为2的自由群的直积同构的子群，分别为L1、L2和L3，其中，L1＝<σ1 2,σ2 2,σ4 2,σ5 2>，L2＝<σ2 2,σ3 2,σ5 2,σ6 2>，L3＝<σ3 2,σ4 2,σ6 2,σ7 2>；再根据子群L1元素，可以生成子群M1：M1＝<σ1 2σ4 2,σ2 2σ5 2,S1v,T1v>；根据子群L2元素，可以生成子群M2：M2＝<σ2 2σ5 2,σ3 2σ6 2,S2v,T2v>；根据子群L3的元素，可以生成子群M3：M3＝<σ3 2σ6 2,σ4 2σ7 2,S3v,T3v>。此时，由于生成了子群M1、M2和M3，所以第一设备可以从中选取子群M1或子群M2或子群M3作为子群P。同理，第二设备也可以从中选取子群M1或子群M2或子群M3作为子群Q。
依次类推，当n的取值更大时，相应地，u的取值范围更大，则辫群Bn含有与两个更多个秩为2的自由群的直积同构的子群Lu；再根据不同的子群Lu的元素，可以相应生成不同的子群Mu。此时，由于生成了多个子群Mu，所以第一设备从中可以选取任一一个子群Mu作为子群P，第二设备也从中选取任一一个子群Mu作为子群Q。当然，第一设备和第二设备可以选取相同的子群Mu作为子群P和子群Q，也可以选取不同的子群Mu作为子群P和子群Q，本申请对此不作特殊限制。
在此基础上，第一设备从子群P中选取一个元素x作为第一私钥x，即第一设备从子群Mu中选取一个元素x作为第一私钥x；第二设备从子群Q中选取一个元素作为第二私钥y，即第二设备从子群Mu中选取一个元素作为第二私钥y。
S25、第一设备将第一私钥与公钥的每个元素计算得到的x-1σ1x,x-1σ2x,...,x-1σn- 1x发送给第二设备。
S26、第二设备将第二私钥与公钥中的每个元素计算得到的y-1σ1y,y-1σ2y,...,y-1σn-1y发送给第一设备。
S27、第一设备接收到第二设备发送的y-1σ1y,y-1σ2y,...,y-1σn-1y后，将第一设备的第一私钥中的所有σk替换为y-1σky，得到fx(y-1σ1y,y-1σ2y,...,y-1σn-1y)＝y-1xy，并计算得到共享密钥为x-1y-1xy。
S28、第二设备接收到第一设备发送的x-1σ1x,x-1σ2x,...,x-1σn-1x后，将第二设备的第二私钥y中的所有σk替换为x-1σkx，得到fy(x-1σ1x,x-1σ2x,...,x-1σn-1x)＝x-1yx，并计算得到共享密钥x-1y-1xy。
可选地，子群P和子群Q均为具有子群成员不可解的Mihailova子群。
由此，可以理解的是，上述子群P和子群Q为Mihailova子群，即，说明作为子群P和子群Q的子群Mu为Mihailova子群，那么，所有子群Mu的成员问题是不可解的。
需要说明的是，子群成员问题(membership problem or generalized wordproblem)指的是：给定群G的一个其生成元集为X的子群H,判定G中任意元素g是否可由X上的字代表,即判定g是否为H中元素。
假若第三方试图攻击第一设备和第二设备建立的公钥密码协议，第三方只能通过第一设备和第二设备的公开信息<σ1,σ2,…,σn-1>，以及通过信道获得的{x-1σ1x,x-1σ2x,...,x-1σn-1x}和{y-1σ1y,y-1σ2y,...,y-1σn-1y}实施攻击。
假若第三方能得到辫群Bn的元素s和t，使得s-1σis＝y-1σiy，t-1σit＝x-1σix，i＝1,2,…,n-1。
令s＝cy,t＝dx,那么有s-1σis＝(cy)-1σicy＝y-1c-1σicy＝y-1σiy，i＝1,2,…,n-1。从而有c-1σic＝σi，i＝1,2,…,n-1。即c与每一个σi乘法可交换。
由于Bn由σ1,σ2,…,σn-1所生成，c是Bn中心的元素。而Bn的中心是由Δ2所生成的无限循环子群<Δ2>,其中，Δ＝σ1σ2…σn-1σ1σ2…σn-2…σ1σ2σ3σ1σ2σ1。从而c是<Δ2>的元素。同理，d也是<Δ2>的元素。
由于<Δ2>是Bn的中心，而σi 2<Δ2>,σi+1 2<Δ2>,σi+3 2<Δ2>和σi+4 2<Δ2>生成的商群Bn/<Δ2>的子群与σi 2,σi+1 2,σi+3 2和σi+4 2生成Bn的子群同构，从而也是秩为2的自由群。所以，子商群(Mi<Δ2>)/<Δ2>也是商群Bn/＜Δ2>的Mihailova子群。故(Mi<Δ2>)/<Δ2>的子群成员问题也是不可解的。
由此，第三方攻击者如果能获得Bn的元素s和t使得s-1σis＝y-1σiy,t-1σit＝x-1σit,i＝1,2,…,n-1。那么s＝cy,t＝dx，c,d∈<Δ2>,所以，在商群Bn/<Δ2>中有s<Δ2>＝y<Δ2>和t<Δ2>＝x<Δ2>。即，第三方攻击者在商群Bn/<Δ2>中必须找到Mihailova子群(Mi＜Δ2>)/<Δ2>中元素y<Δ2>和x<Δ2>。但是，由于(Mi<Δ2>)/<Δ2>的子群成员问题是不可解的，所以，不存在算法使得攻击者能成功获得y<Δ2>和x<Δ2>，从而也不存在算法使得攻击者能成功获得所需的s和t。
本申请实施例提供了一种建立共享密钥的方法，基于第一设备和第二设备确定指数为n的辫群Bn作为双方公钥；双方分别从辫群Bn中选取一个子群，以及将子群中的一个元素作为自己的私钥；再将各自的私钥与公钥的每一元素进行共轭计算；然后，双方分别将各自的共轭结果发送给对方，再根据共轭结果计算得到共享密钥。由于引入的子群的成员问题是不可解的，因此，所建立的共享密钥的的方法的安全性在理论上得到充分证明，可以量子计算攻击等各种攻击。
应理解，上述实施例中各步骤的序号的大小并不意味着执行顺序的先后，各过程的执行顺序应以其功能和内在逻辑确定，而不应对本申请实施例的实施过程构成任何限定。
本申请实施例还提供一种建立共享密钥的装置，如图3所示，应用于第一设备，建立共享密钥的装置10包括处理单元11和收发单元12。
处理单元11，用于确定指数为n的辫群Bn为公钥。
其中，Bn＝<σ1,σ2,…,σn-1|σiσj＝σjσi,|i-j|≥2,σiσi+1σi＝σi+1σiσi+1,1≤i≤n-2>；辫群Bn中的每个元素均以集合{σ1,σ2,…,σn-1}上代表该元素的字表示，且字具有唯一性的正规形式，n≥6，n为整数。
该处理单元11还用于选取辫群Bn的多个元素生成的一个子群P，并从子群P中选取一个元素x作为第一私钥，其中，对x的限定为x＝fx(σ1,σ2,…,σn-1)。
收发单元12，用于接收第二设备发送的{y-1σ1y,y-1σ2y,...,y-1σn-1y}；其中，第二设备为与第一设备建立共享密钥的设备，y-1σky是第二设备选取辫群Bn的多个元素生成的一个子群Q，并从子群Q中选取一个元素y作为第二私钥，根据第二私钥与公钥中的每个元素计算得到的；其中，对y的限定为y＝fy(σ1,σ2,…,σn-1)；k＝1,2,…,n-1。
该收发单元12还用于将第一私钥x与公钥的每个元素计算得到的{x-1σ1x,x-1σ2x,...,x-1σn-1x}发送给第二设备，以使得第二设备将第二私钥y中的所有σk替换为x-1σkx，得到fy(x-1σ1x,x-1σ2x,...,x-1σn-1x)＝x-1yx，并计算得到共享密钥x-1y-1xy；
处理单元，还用于将第一设备的第一私钥x中的所有σk替换为y-1σky，得到fx(y-1σ1y,y-1σ2y,...,y-1σn-1y)＝y-1xy，并计算得到共享密钥为x-1y-1xy。
可选地，处理单元11，用于选取辫群Bn的多个元素生成的一个子群P，包括：
辫群Bn含有与两个秩为2的自由群的直积同构的子群Lu：Lu＝<σu 2,σu+1 2,σu+3 2,σu+4 2>；u＝1,2,...,n-5；
处理单元11，用于根据子群Lu的元素，生成子群Mu：Mu＝<σu 2σu+3 2,σu+1 2σu+4 2,Suv,Tuv>；v＝1,2,...,27；
还用于选取一个子群Mu作为子群P。
当u＝1,2,...,n-5时，27个Suv分别为：
Figure BDA0002478388390000201
Figure BDA0002478388390000202
Figure BDA0002478388390000203
Figure BDA0002478388390000204
Figure BDA0002478388390000205
Figure BDA0002478388390000206
Figure BDA0002478388390000207
Figure BDA0002478388390000208
Figure BDA0002478388390000209
Figure BDA00024783883900002010
Figure BDA00024783883900002011
Figure BDA00024783883900002012
Figure BDA00024783883900002013
Figure BDA00024783883900002014
Figure BDA0002478388390000211
Figure BDA0002478388390000212
Figure BDA0002478388390000213
Figure BDA0002478388390000214
Figure BDA0002478388390000215
Figure BDA0002478388390000216
Figure BDA0002478388390000217
Figure BDA0002478388390000218
Figure BDA0002478388390000219
Figure BDA00024783883900002110
Figure BDA0002478388390000221
Figure BDA0002478388390000222
Figure BDA0002478388390000223
Figure BDA0002478388390000224
Figure BDA0002478388390000225
将所述27个Suv中的σu替换为σu+3，σu+1替换为σu+4得到对应的27个Tuv。
本申请实施例提供的建立共享密钥的装置，与上述建立共享密钥的方法具有相同的有益效果，在此不再赘述。
本申请实施例还提供一种计算机设备，如图4所示，该计算机设备40包括：存储器41、处理器42以及存储在所述存储器中并可在所述处理器上运行的计算机程序43，处理器执行计算机程序时实现如上所述的建立共享密钥的方法。
本申请实施例还提供一种计算机可读存储介质，所述计算机可读存储介质存储有计算机程序，所述计算机程序被处理器执行时实现如上所述的建立共享密钥的方法。
本申请实施例提供了一种计算机程序产品，当计算机程序产品在计算机设备上运行时，使得计算机设备执行时可实现上述建立共享密钥的方法。
本领域普通技术人员可以意识到，结合本文中所公开的实施例描述的各示例的单元及算法步骤，能够以电子硬件、或者计算机软件和电子硬件的结合来实现。这些功能究竟以硬件还是软件方式来执行，取决于技术方案的特定应用和设计约束条件。专业技术人员可以对每个特定的应用来使用不同方法来实现所描述的功能，但是这种实现不应认为超出本申请的范围。
以上所述实施例仅用以说明本申请的技术方案，而非对其限制；尽管参照前述实施例对本申请进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本申请各实施例技术方案的精神和范围，均应包含在本申请的保护范围之内。

Claims (10)

1.一种建立共享密钥的方法，其特征在于，包括：
第一设备确定指数为n的辫群Bn为公钥；
其中，Bn＝<σ1,σ2,…,σn-1|σiσj＝σjσi,|i-j|≥2,σiσi+1σi＝σi+1σiσi+1,1≤i≤n-2>；所述辫群Bn中的每个元素均以集合{σ1,σ2,…,σn-1}上代表该元素的字表示，且所述字具有唯一性的正规形式，n≥6，n为整数；
所述第一设备选取辫群Bn的多个元素生成的一个子群P，并从子群P中选取一个元素x作为第一私钥，其中，对x的限定为x＝fx(σ1,σ2,…,σn-1)；
所述第一设备接收第二设备发送的{y-1σ1y,y-1σ2y,...,y-1σn-1y}；其中，所述第二设备为与所述第一设备建立共享密钥的设备，y-1σky是所述第二设备选取辫群Bn的多个元素生成的一个子群Q，并从子群Q中选取一个元素y作为第二私钥，根据第二私钥与所述公钥中的每个元素计算得到的；其中，对y的限定为y＝fy(σ1,σ2,…,σn-1)；k＝1,2,…,n-1；
所述第一设备将所述第一私钥与所述公钥的每个元素计算得到的{x-1σ1x,x-1σ2x,...,x-1σn-1x}发送给第二设备，以使得第二设备将所述第二私钥y中的所有σk替换为x-1σkx，得到fy(x-1σ1x,x-1σ2x,...,x-1σn-1x)＝x-1yx，并计算得到共享密钥x-1y-1xy；
将所述第一设备的第一私钥中的所有σk替换为y-1σky，得到fx(y-1σ1y,y-1σ2y,...,y-1σn- 1y)＝y-1xy，并计算得到共享密钥为x-1y-1xy。
2.根据权利要求1所述的建立共享密钥的方法，其特征在于，所述第一设备选取辫群Bn的多个元素生成的一个子群P，包括：
所述辫群Bn含有与两个秩为2的自由群的直积同构的子群Lu：Lu＝<σu 2,σu+1 2,σu+3 2,σu+4 2>；u＝1,2,...,n-5；
根据所述子群Lu的元素，生成子群Mu：Mu＝<σu 2σu+3 2,σu+1 2σu+4 2,Suv,Tuv>；v＝1,2,...,27；
选取一个所述子群Mu作为所述子群P。
3.根据权利要求2所述的建立共享密钥的方法，其特征在于，当u＝1,2,...,n-5时，27个Suv分别为：
Figure FDA0002478388380000031
Figure FDA0002478388380000032
Figure FDA0002478388380000033
Figure FDA0002478388380000034
Figure FDA0002478388380000035
Figure FDA0002478388380000036
Figure FDA0002478388380000037
Figure FDA0002478388380000038
Figure FDA0002478388380000039
Figure FDA00024783883800000310
Figure FDA00024783883800000311
Figure FDA00024783883800000312
Figure FDA00024783883800000313
Figure FDA00024783883800000314
Figure FDA0002478388380000041
Figure FDA0002478388380000042
Figure FDA0002478388380000043
Figure FDA0002478388380000044
Figure FDA0002478388380000045
Figure FDA0002478388380000046
Figure FDA0002478388380000047
Figure FDA0002478388380000048
Figure FDA0002478388380000049
Figure FDA00024783883800000410
Figure FDA0002478388380000051
Figure FDA0002478388380000052
Figure FDA0002478388380000053
Figure FDA0002478388380000054
Figure FDA0002478388380000055
4.根据权利要求3所述的建立共享密钥的方法，其特征在于，将所述27个Suv中的σu替换为σu+3，σu+1替换为σu+4得到对应的27个Tuv。
5.根据权利要求1所述的建立共享密钥的方法，其特征在于，所述子群P和所述子群Q均为具有子群成员不可解的Mihailova子群。
6.一种建立共享密钥的装置，应用于第一设备，所述建立共享密钥的装置包括处理单元和收发单元；
所述处理单元，用于确定指数为n的辫群Bn为公钥；
其中，Bn＝<σ1,σ2,…,σn-1|σiσj＝σjσi,|i-j|≥2,σiσi+1σi＝σi+1σiσi+1,1≤i≤n-2>；所述辫群Bn中的每个元素均以集合{σ1,σ2,…,σn-1}上代表该元素的字表示，且所述字具有唯一性的正规形式，n≥6，n为整数；
还用于选取辫群Bn的多个元素生成的一个子群P，并从子群P中选取一个元素x作为第一私钥，其中，对x的限定为x＝fx(σ1,σ2,…,σn-1)；
所述收发单元，用于接收第二设备发送的{y-1σ1y,y-1σ2y,...,y-1σn-1y}；其中，所述第二设备为与所述第一设备建立共享密钥的设备，y-1σky是所述第二设备选取辫群Bn的多个元素生成的一个子群Q，并从子群Q中选取一个元素y作为第二私钥，根据第二私钥与所述公钥中的每个元素计算得到的；其中，对y的限定为y＝fy(σ1,σ2,…,σn-1)；k＝1,2,…,n-1；
还用于将所述第一私钥与所述公钥的每个元素计算得到的{x-1σ1x,x-1σ2x,...,x-1σn- 1x}发送给第二设备，以使得第二设备将所述第二私钥y中的所有σk替换为x-1σkx，得到fy(x-1σ1x,x-1σ2x,...,x-1σn-1x)＝x-1yx，并计算得到共享密钥x-1y-1xy；
所述处理单元，还用于将所述第一设备的第一私钥中的所有σk替换为y-1σky，得到fx(y-1σ1y,y-1σ2y,...,y-1σn-1y)＝y-1xy，并计算得到共享密钥为x-1y-1xy。
7.根据权利要求6所述的建立共享密钥的装置，其特征在于，所述处理单元，用于选取辫群Bn的多个元素生成的一个子群P，包括：
所述辫群Bn含有与两个秩为2的自由群的直积同构的子群Lu：Lu＝<σu 2,σu+1 2,σu+3 2,σu+4 2>；u＝1,2,...,n-5；
所述处理单元，用于根据所述子群Lu的元素，生成子群Mu：Mu＝<σu 2σu+3 2,σu+1 2σu+4 2,Suv,Tuv>；v＝1,2,...,27；
还用于选取一个所述子群Mu作为所述子群P。
8.根据权利要求7所述的建立共享密钥的装置，其特征在于，当u＝1,2,...,n-5时，27个Suv分别为：
Figure FDA0002478388380000071
Figure FDA0002478388380000072
Figure FDA0002478388380000073
Figure FDA0002478388380000074
Figure FDA0002478388380000075
Figure FDA0002478388380000076
Figure FDA0002478388380000077
Figure FDA0002478388380000078
Figure FDA0002478388380000079
Figure FDA00024783883800000710
Figure FDA00024783883800000711
Figure FDA00024783883800000712
Figure FDA00024783883800000713
Figure FDA00024783883800000714
Figure FDA0002478388380000081
Figure FDA0002478388380000082
Figure FDA0002478388380000083
Figure FDA0002478388380000084
Figure FDA0002478388380000085
Figure FDA0002478388380000086
Figure FDA0002478388380000087
Figure FDA0002478388380000088
Figure FDA0002478388380000089
Figure FDA00024783883800000810
Figure FDA0002478388380000091
Figure FDA0002478388380000092
Figure FDA0002478388380000093
Figure FDA0002478388380000094
Figure FDA0002478388380000095
将所述27个Suv中的σu替换为σu+3，σu+1替换为σu+4得到对应的27个Tuv。
9.一种计算机设备，包括存储器、处理器以及存储在所述存储器中并可在所述处理器上运行的计算机程序，其特征在于，所述处理器执行所述计算机程序时实现如权利要求1至5任一项所述的建立共享密钥的方法。
10.一种计算机可读存储介质，所述计算机可读存储介质存储有计算机程序，其特征在于，所述计算机程序被处理器执行时实现如权利要求1至5任一项所述的建立共享密钥的方法。
CN202010371284.0A 2020-05-06 2020-05-06 建立共享密钥的方法及装置 Active CN111740821B (zh)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN202010371284.0A CN111740821B (zh) 2020-05-06 2020-05-06 建立共享密钥的方法及装置

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN202010371284.0A CN111740821B (zh) 2020-05-06 2020-05-06 建立共享密钥的方法及装置

Publications (2)

Publication Number Publication Date
CN111740821A true CN111740821A (zh) 2020-10-02
CN111740821B CN111740821B (zh) 2023-06-27

Family

ID=72647004

Family Applications (1)

Application Number Title Priority Date Filing Date
CN202010371284.0A Active CN111740821B (zh) 2020-05-06 2020-05-06 建立共享密钥的方法及装置

Country Status (1)

Country Link
CN (1) CN111740821B (zh)

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN114221753A (zh) * 2021-11-23 2022-03-22 深圳大学 密钥数据处理方法和电子设备
WO2023159849A1 (zh) * 2022-02-25 2023-08-31 深圳大学 一种数字签名方法、计算机设备及介质

Citations (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN103414569A (zh) * 2013-08-21 2013-11-27 王威鉴 一种建立抗攻击的公钥密码的方法
US20180013554A1 (en) * 2016-07-06 2018-01-11 Securerf Corporation Shared secret communication system with use of cloaking elements
CN107911209A (zh) * 2017-12-28 2018-04-13 深圳大学 建立抗量子计算攻击的安全性公钥密码的方法
CN108768639A (zh) * 2018-06-06 2018-11-06 电子科技大学 一种公钥保序加密方案
CN109787752A (zh) * 2018-09-30 2019-05-21 王威鉴 建立抗攻击的共享密钥的方法
US20190215148A1 (en) * 2018-01-11 2019-07-11 Shenzhen University Method of establishing anti-attack public key cryptogram

Patent Citations (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN103414569A (zh) * 2013-08-21 2013-11-27 王威鉴 一种建立抗攻击的公钥密码的方法
US20180013554A1 (en) * 2016-07-06 2018-01-11 Securerf Corporation Shared secret communication system with use of cloaking elements
CN107911209A (zh) * 2017-12-28 2018-04-13 深圳大学 建立抗量子计算攻击的安全性公钥密码的方法
US20190215148A1 (en) * 2018-01-11 2019-07-11 Shenzhen University Method of establishing anti-attack public key cryptogram
CN108768639A (zh) * 2018-06-06 2018-11-06 电子科技大学 一种公钥保序加密方案
CN109787752A (zh) * 2018-09-30 2019-05-21 王威鉴 建立抗攻击的共享密钥的方法

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
程玉芳等: "辫群上的扭结共轭搜索问题和密码体制研究", 《计算机工程》 *

Cited By (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN114221753A (zh) * 2021-11-23 2022-03-22 深圳大学 密钥数据处理方法和电子设备
WO2023093004A1 (zh) * 2021-11-23 2023-06-01 深圳大学 密钥数据处理方法和电子设备
CN114221753B (zh) * 2021-11-23 2023-08-04 深圳大学 密钥数据处理方法和电子设备
WO2023159849A1 (zh) * 2022-02-25 2023-08-31 深圳大学 一种数字签名方法、计算机设备及介质

Also Published As

Publication number Publication date
CN111740821B (zh) 2023-06-27

Similar Documents

Publication Publication Date Title
CN107911209B (zh) 建立抗量子计算攻击的安全性公钥密码的方法
CN112769542B (zh) 基于椭圆曲线的乘法三元组生成方法、装置、设备及介质
US20220166614A1 (en) System and method to optimize generation of coprime numbers in cryptographic applications
Wohlwend Elliptic curve cryptography: Pre and post quantum
CN117795901A (zh) 生成数字签名份额
CN111740821A (zh) 建立共享密钥的方法及装置
WO2023159849A1 (zh) 一种数字签名方法、计算机设备及介质
WO2022116175A1 (zh) 数字签名的生成方法、装置和服务器
US11743036B2 (en) Method and apparatus for establishing shared key
CN111614465B (zh) 基于超奇异同源秘钥封装协议的公钥生成方法和装置
US20190215148A1 (en) Method of establishing anti-attack public key cryptogram
CN114221753B (zh) 密钥数据处理方法和电子设备
JP2005055488A (ja) 楕円曲線暗号におけるスカラー倍計算方法と、その装置およびそのプログラム
CN118842594A (zh) 批量验证密文的方法和计算设备
US11616994B2 (en) Embedding information in elliptic curve base point
WO2024038028A1 (en) Improved blockchain system and method
Yang et al. Quantum public-key cryptosystems based on induced trapdoor one-way transformations
Luengo et al. DME: a full encryption, signature and KEM multivariate public key cryptosystem
CN111147254B (zh) 两方协同的EdDSA数字签名生成方法和装置
JP2002508523A (ja) 楕円曲線上の高速有限体演算
Karmakar et al. VDOO: A Short, Fast, Post-Quantum Multivariate Digital Signature Scheme
Faraoun A novel verifiable and unconditionally secure (m, t, n)-threshold multi-secret sharing scheme using overdetermined systems of linear equations over finite Galois fields
CN115840953B (zh) 一种身份认证方法、装置、终端及可读存储介质
CN118945157B (zh) 一种基于输入输出系统文件的传输方法、设备及存储介质
JP2005316038A (ja) 楕円曲線暗号におけるスカラー倍計算方法と、その装置およびプログラム

Legal Events

Date Code Title Description
PB01 Publication
PB01 Publication
SE01 Entry into force of request for substantive examination
SE01 Entry into force of request for substantive examination
GR01 Patent grant
GR01 Patent grant