模指数外包方案ExpSOS的格基密码分析

doi:10.3778/j.issn.1673-9418.2011052

计算机科学与探索 ›› 2022, Vol. 16 ›› Issue (5): 1087-1095.DOI: 10.3778/j.issn.1673-9418.2011052

模指数外包方案ExpSOS的格基密码分析

郑云海¹, 田呈亮¹^,²^,⁺()

1.青岛大学计算机科学技术学院,山东青岛 266071
2.中国科学院信息工程研究所信息安全国家重点实验室,北京 100093

收稿日期:2020-11-18 修回日期:2021-01-14 出版日期:2022-05-01 发布日期:2022-05-19
通讯作者: + E-mail: tianchengliang@qdu.edu.cn
作者简介:郑云海（1995—）,男,山东潍坊人,硕士研究生,主要研究方向为云计算安全、密码学。
田呈亮（1983—）,男,山东莱芜人,博士,副教授,主要研究方向为基于格的密码学、云/边缘计算中的隐私保护问题。
基金资助:
国家自然科学基金(61702294);国家密码发展基金(MMJJ20170126);信息安全国家重点实验室开放课题(2016-MS-23)

Lattice-Based Cryptanalysis on Outsourcing Scheme of Modular Exponentiations ExpSOS

ZHENG Yunhai¹, TIAN Chengliang¹^,²^,⁺()

1. College of Computer Science & Technology, Qingdao University, Qingdao, Shandong 266071, China
2. State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China

Received:2020-11-18 Revised:2021-01-14 Online:2022-05-01 Published:2022-05-19
About author:ZHENG Yunhai, born in 1995, M.S. candidate. His research interests include cloud computing security and cryptography.
TIAN Chengliang, born in 1983, Ph.D., associate professor. His research interests include lattice-based cryptography and privacy preservation problems in cloud/edge computing.
Supported by:
National Natural Science Foundation of China(61702294);National Development Foundation of Cryptography(MMJJ20170126);Open Research Project of State Key Laboratory of Information Security(2016-MS-23)

摘要/Abstract

摘要：

随着云计算的普及,外包计算作为一种重要的云服务形式,日益引起学术界与工业界的广泛关注。模指数操作作为一种耗时的基本密码运算广泛地应用于RSA、数字签名算法（DSA）等,其外包方案的设计得到了广泛关注和研究。当前基于单个云服务器的外包方案,大多需要在本地端执行一个小指数的模指数操作,一般地,该指数的大小决定了方案的效率,其机密性决定着方案的安全性。对Zhou等提出的一个单服务器模指数外包方案ExpSOS进行了唯密文安全性分析。通过将算法中底数与指数的机密性转换为求解模多项式的小整数解的问题,使用Coppersmith的格构造技术对ExpSOS方案潜在的弱密钥进行了全面分析,并分别估计了安全应用场景下方案适用的底数大小和方案中安全参数选取的规模,为该方案在实际应用中的安全部署提出了具体建议。最后,给出了数字签名标准推荐参数下的ExpSOS方案弱密钥攻击实例,证明了理论攻击的有效性。

关键词: 外包计算, 模指数, 唯密文攻击, Coppersmith算法, 格基约化

Abstract:

With the popularity of cloud computing, outsourcing computing, as an important form of cloud service, has attracted more and more attention from academia and industry. As a time-consuming basic cryptographic operation, modular exponential operation is widely used in RSA, digital signature algorithm (DSA), etc. The design of its outsourcing scheme has received extensive attention and research. At present, most of the outsourcing schemes based on a single cloud server need to perform a small exponential operation on the local. Generally, the size of the exponential determines the efficiency of the scheme, and its confidentiality determines the security of the scheme. This paper gives ciphertext-only security analysis on Zhou et al’s modular exponentiation outsourcing scheme ExpSOS. By converting the problem of recovering the base and exponent in their algorithm to the problem of finding small root of polynomial modular unknown divisors, this paper analyzes the potential weak keys of ExpSOS by invoking Coppersmith’s lattice-based construction technique, and estimates the size of the secure base and the size of the security parameters in the scheme. Further, the specific suggestions for the security deployment of the scheme in practical application are put forward. Finally, some practical attack examples of weak key in ExpSOS scheme are given, which confirms the effectiveness of the theoretical attack.

Key words: computation outsourcing, modular exponentiations, ciphertext-only attack, Coppersmith’s method, lattice basis reduction

中图分类号:

TP309.7

郑云海, 田呈亮. 模指数外包方案ExpSOS的格基密码分析[J]. 计算机科学与探索, 2022, 16(5): 1087-1095.

ZHENG Yunhai, TIAN Chengliang. Lattice-Based Cryptanalysis on Outsourcing Scheme of Modular Exponentiations ExpSOS[J]. Journal of Frontiers of Computer Science and Technology, 2022, 16(5): 1087-1095.

图/表 5

表1 符号说明

Table 1 Symbol description

符号	说明
$R m$	$m$ 维实数向量集
$Z$	整数集
$Z n$	$n$ 维整数向量集
$d e t (·)$	行列式函数
$\| \| · \| \|$	欧氏范数
$φ (·)$	欧拉函数
$e$	欧拉常数
$l b$	以2为底的对数

表1 符号说明

Table 1 Symbol description

符号	说明
$R m$	$m$ 维实数向量集
$Z$	整数集
$Z n$	$n$ 维整数向量集
$d e t (·)$	行列式函数
$\| \| · \| \|$	欧氏范数
$φ (·)$	欧拉函数
$e$	欧拉常数
$l b$	以2为底的对数

表2 变量上界

Table 2 Upper-bounds of variables

变量	上界	变量	上界
$k 1$	$X K$	$k 2$	$X K$
$t 1$	$X T$	$t 2$	$X T$
$a$	$X A$	$u$	$X U$
$t 1 a$	$X t 1 a$	$t 1 k 1 - k 2$	$X t 1 k 1 - k 2$
$u 0$	$X u 0$	$u 1$	$X u 1$

表2 变量上界

Table 2 Upper-bounds of variables

变量	上界	变量	上界
$k 1$	$X K$	$k 2$	$X K$
$t 1$	$X T$	$t 2$	$X T$
$a$	$X A$	$u$	$X U$
$t 1 a$	$X t 1 a$	$t 1 k 1 - k 2$	$X t 1 k 1 - k 2$
$u 0$	$X u 0$	$u 1$	$X u 1$

表3 安全参数的选取范围

Table 3 Selection range of security parameters

安全参数	$N$ 为素数	$N$ 为合数
$l b u$	$l b u ≥ 0.5 l b N, l b u 0 u 1 ≥ 0.414 l b N$	$l b u ≥ 23 l b N, l b u 0 u 1 ≥ 0.577 l b N$
$l b u 0 u 1$	$l b u ≥ 0.5 l b N, l b u 0 u 1 ≥ 0.414 l b N$	$l b u ≥ 23 l b N, l b u 0 u 1 ≥ 0.577 l b N$
$l b k 1 a$	$l b k 1 a ≥ 0.414 l b N$	$l b k 1 a ≥ 0.077 l b N$
$l b t 1 t 2 k 2 a$	$l b t 1 t 2 k 2 a ≥ 0.38 l b N$	$l b t 1 t 2 k 2 a ≥ 0.04 l b N$
$l b k 2 a$	$l b k 2 a ≥ 0.38 l b N - 2 l b b$	$l b k 2 a ≥ 0.04 l b N - 2 l b b$
$l b (t 1 k 1 - k 2)$

表3 安全参数的选取范围

Table 3 Selection range of security parameters

安全参数	$N$ 为素数	$N$ 为合数
$l b u$	$l b u ≥ 0.5 l b N, l b u 0 u 1 ≥ 0.414 l b N$	$l b u ≥ 23 l b N, l b u 0 u 1 ≥ 0.577 l b N$
$l b u 0 u 1$	$l b u ≥ 0.5 l b N, l b u 0 u 1 ≥ 0.414 l b N$	$l b u ≥ 23 l b N, l b u 0 u 1 ≥ 0.577 l b N$
$l b k 1 a$	$l b k 1 a ≥ 0.414 l b N$	$l b k 1 a ≥ 0.077 l b N$
$l b t 1 t 2 k 2 a$	$l b t 1 t 2 k 2 a ≥ 0.38 l b N$	$l b t 1 t 2 k 2 a ≥ 0.04 l b N$
$l b k 2 a$	$l b k 2 a ≥ 0.38 l b N - 2 l b b$	$l b k 2 a ≥ 0.04 l b N - 2 l b b$
$l b (t 1 k 1 - k 2)$

表4 N为素数时的实验参数及结果

Table 4 Experimental parameters and results while N is prime

名称	数值
$L$	0x7810B36D 4CDDCD6D DE8AEFA5 E8B09DC4 094CA47D 117907B6 BB3256DD 78EEF3F1 BA78FE91 5BAEC309 4D69DE5A 7603037D C09D16D4 A72C8258 808AC8AD 7D63296B B65F9F45 B20745E6 DC1C894C FF221967 A9F4948A 77DA3976 9BE92EB5 2CFC07C0 B0CD5238 658E5C2D 582EAEFA 071E4C64 2FB4F5B4 3BE3C169 0BD03E75 71731B39 D816CD71 72201474 45DC8C79 1A218E06 EF794F68 0EF0D2D3 D712D41B 0D6C86AB 0ED9BD4F 4E328531 DEEE8FA8 E93B5371 F04C8EFE D6C65A16 7E07713E 694B4918 DAB2439C 6838D90A E5FEF426 4C12557F 86319DD0 817C8ACD 72292C7B 3BF55C37 184E04F3 8ABE45CE C790245E 12CFA0E3 C2AD7805 E4DC1AE3 ECC0D96F 050E089D 44AE275C BAAD5378 E64625DE 3178547 5518E765 FF6C2CBE 667B7E39 51B8587B AD49701F 4163C222 AF8D5959 CF253E32 9274A53E 000634FD 786A0A87 62E2D9BF 2177965A 8C1873AC 2E96ABAA D75785B9 4561C100 1CE4E7B9 A603C0BF A0376FB8 D1871A32 80773432 177D3ED0 9A779A6F 25EF86F3 231B07A2 51D8D75E EBB719D3 1BCE8EFD 00D36A65 52BB9BE4 0EA453D8 4876B7D4 769DA3DA D358D42B 84FFD5A0 C0AC4FB6 63FFFDFD B28D1DF2 AEC677E7 169BEF14 12F70130 5298B5C3 2916ACFB 96859E64 7679B3CD 124DF94E 68594C21 DFE7DC79 4A58F093 07151AD6 BA04871D 28B52789 85740ACA 487956B7 F83E9001 9DD62BB0 37411D9F E75E4481 D0B251DA 1100F01A 9AF24F2F 2C02A2BB F28BFC31 3395A495 63763FAD 8A25AAB0 2CE8C0D9 2B3C0B36 C4FCBEE0 B56C0952 60F264BA B55F6C84 C0716294 510D644C 22A1CFB7 ABA77416 2F5C4789 0B9B9990 25B901DC EA838AB7 6DF1A602 3985142B 66BFACD0 17964990 3A2D2E18 E624247D B3E3D9BA C319197C 553E31D8 F3D75E65 8556A972 DC588FCB 1D4F7712 087241C1 9F535365 A59563B3 7E587186 F0A8B7F8 27104D45 3CEA7A18 C9469FF4 A8C92621 FCAD85CE 1053A568 8BF0F5EC 3581208F 5F40FB99 E1997B76 3055ABDF 490937FC FDB10EBE 30DB293B 96B8F948 51D1395F 711FA945 D919499E 7146936E F17A5166 C0FF39DF 04748203 F3E0CD0A 2AEB73D0 EBE40BC5
$U$	0x5FC6F7AB D3978738 A06742E5 75B3CDFF 7BDA7C91 5336F771 A7C46FD2 9A87B0FE E0AA810A 48C6F11E 1D6A10B9 C5DA251A 3C49B831 517FF01B DCDE01F7 A7F8321E 1747DE98 F77DFF4B A5052CB9 51629AA0 52A6F3D8 73C1FEFF F9690E2D E94C4ACA 9D568E52 55AEAB51 E964FEB7 0D2A6875 D5CAAB7E 82A63305 97B602E8 ED33AD0E EF9A90E1 F188A8D3 C2E01CE9 0D6F65EA 9B2881C0 01994011 03B84B6C DB129ACD DAF2124F 0965CC33 42E95682 A5308C4C 58AAD1D2 A91439FB DFED8CCE EEEF2FE6 CFBF15BE F497F000 41D2F60C C8CF2E96 4CE82B30 902DF17D 6E125EFA 1C5BD841 E66147D3 8A1AB88A 61541542 5A133023 5554E980 95637068 5919DE2B 793A0D1D B8D99B84 F2253BD3 351AD8FD F715AFD1 6A43A533 CB01ECCB 41E532D1 7B4D72A4 5F00CCB1 27CE38A1 19866557 B877B29C BD921E95 78570525 170E50E2 A0A3E391 04F024AE D1192AA D0527A2 18FB9C1C B40C15D1 9B79DEE3 F1A241A6 409623B9 7CEE9008 5C8C8A50 5CD12879 C510C360 4CB4459B 181F373A 78520CC7 87FD767C 1FD4C6B6 6249CE55 6691633A 7DFB3C3F BBD56DA4 FD489DF9 CB05631E F6293B4B 30DCDED5 8BBE87A8 AB0542EB AFF05ECC F7A8000F 273E3DD7 66D57C61 77296749 EAA49BDD 00B4F8F4 B1A6B0CF 0120DA9E 6FADCB8A 8D87A849 2E5613B8 AE8B1D7C 0F168027 BD6CD0EF 74A47FBD 7C91C0DB E2FC5F25 1F517BE1 353FD0BE 1C1EDABC 1D067DAC 8EFEB536 DEEF9DD6 23CD4CCF 57A60697 EC3716DB C244D8E1 F89BF6D3 B00915A0 7B3286EA C8AB79AC 35B96F5E CC6D7172 41296197 DB61BF78 3DC6DB48 2D8AAD43 9B31B6EB C6287817 010E571F 47A8D947 CFA160DE 398EDDD5 AAA6C489 5A7B0B95 6F962A9D 6629E8AB 5A1747FD 805A7A95 05BC2661 93EDD35B 1CF82140 FCD53A05 341B9B74 A7321895 86D409D2 B248D1A8 461DD94A 2BEAEB88 48F2DBE4 D42BE0BE 601B516F DCA03DE3 C69C17BB 13B6914A 7CBAC4AF B66160B0 9AB06327 545B8C6D 9838C036 0A9E2EED 056376AC 778221A8 C83D5813 D3780DF9 F425E2D1 9A83DDE9 426CE764 3206166C B476D23A 82BD2050 94A3BBE6 860F51D2 01D4CB68
名称	数值
$A 1$	0x86AC816C A208E159 A6C15DEC 985F2B39 32F7491B AA67C602 47F24157 9E99229 470CC3A7 6759065D E14D01F8 79CC50A6 CF8AE298 1149D2C9 39E936B1 0AA5FB4D 4CE18790 4918028D B81D1B08 16A1F57F 6B20E02B 8A8113A0 2C464291 18137CBD 58B857B7 F4CC016B 1D66C6D7 CD77BBF4 8FF25C0E 74DFE992 719D2F5 E20390FD BF5173D4 BAB558C7 308687EE 13275A36 13B06231 6878C5BE 8F2147C8 D54D60D3 E1B3D200 58896D9D 46A89FA6 A8ED8759 E2F69C21 74AE840A 73717A46 F8032E67 50691098 73EB53C0 0C979D84 C73428FF 9979852B 042433D2 AD90A0E6 4A87E3F6 BA8AF0ED F89D224C 2CEBBD42 726201AC 26A5B1D2 015A5D3E 2112CAC ACC9104 7AEEB973 ACE66A96 6FE3CD60 1D2D36C1 9AE31AA4 EEF751A 74C1855B E4C30D31 6B8DB258 3960AC01 E6F1AFBA FA400309 B8DACA2D 5F1D69B 73A79B1 6A344384 CDD69C88 AFB7B32B 949BE578 74A4C71D 75F48C35 1EC68F31 8A22FE86 D59AB0DD 2ECF14DF 67341921 61C3DD3C 3B78E830 FEA2B76 CBC5F168 3E474E8B 0C9021AB D3FC
$X A$	0x87AE326D 95367438 F5601AD2 8961E264 87730841 3952EA1C DC742402 7EEDC8AD
$X U$	0xD71CE05B F55FA8D9 7B26C1A2 374EB24F 7D173A5C B4031776 1827982C 20D7A85 37640DCB D1574716 163CB7C7 4DF3C271 09B1AB20 0F837E5E 913C0CBD 5BE4B4AC AF342C44 9EB60B04 7E8FD56C 5D854186 F012A17C 338CFA2D 56B3AD4 45465B04 0ACB9690 9AC59B2B FDA1448C 5EA069E0 5056E57D 62E2FE51 F36E68E8 060DFD97
$X K$	0xD0A9
$u$	0xD71CE05B F55FA8D9 7B26C1A2 374EB24F 7D173A5C B4031776 1827982C A20D7A85 37640DCB D1574716 163CB7C7 4DF3C271 09B1AB20 0F837E5E 13C0CBD 5BE4B4AC AF342C44 9EB60B047E8FD56C 5D854186 F012A17C 338CFA2D B56B3AD4 45465B04 0ACB9690 9AC59B2B FDA1448C 5EA069E0 5056E57D 62E2FE51 F36E68E8 060DFD96

表4 N为素数时的实验参数及结果

Table 4 Experimental parameters and results while N is prime

名称	数值
$L$	0x7810B36D 4CDDCD6D DE8AEFA5 E8B09DC4 094CA47D 117907B6 BB3256DD 78EEF3F1 BA78FE91 5BAEC309 4D69DE5A 7603037D C09D16D4 A72C8258 808AC8AD 7D63296B B65F9F45 B20745E6 DC1C894C FF221967 A9F4948A 77DA3976 9BE92EB5 2CFC07C0 B0CD5238 658E5C2D 582EAEFA 071E4C64 2FB4F5B4 3BE3C169 0BD03E75 71731B39 D816CD71 72201474 45DC8C79 1A218E06 EF794F68 0EF0D2D3 D712D41B 0D6C86AB 0ED9BD4F 4E328531 DEEE8FA8 E93B5371 F04C8EFE D6C65A16 7E07713E 694B4918 DAB2439C 6838D90A E5FEF426 4C12557F 86319DD0 817C8ACD 72292C7B 3BF55C37 184E04F3 8ABE45CE C790245E 12CFA0E3 C2AD7805 E4DC1AE3 ECC0D96F 050E089D 44AE275C BAAD5378 E64625DE 3178547 5518E765 FF6C2CBE 667B7E39 51B8587B AD49701F 4163C222 AF8D5959 CF253E32 9274A53E 000634FD 786A0A87 62E2D9BF 2177965A 8C1873AC 2E96ABAA D75785B9 4561C100 1CE4E7B9 A603C0BF A0376FB8 D1871A32 80773432 177D3ED0 9A779A6F 25EF86F3 231B07A2 51D8D75E EBB719D3 1BCE8EFD 00D36A65 52BB9BE4 0EA453D8 4876B7D4 769DA3DA D358D42B 84FFD5A0 C0AC4FB6 63FFFDFD B28D1DF2 AEC677E7 169BEF14 12F70130 5298B5C3 2916ACFB 96859E64 7679B3CD 124DF94E 68594C21 DFE7DC79 4A58F093 07151AD6 BA04871D 28B52789 85740ACA 487956B7 F83E9001 9DD62BB0 37411D9F E75E4481 D0B251DA 1100F01A 9AF24F2F 2C02A2BB F28BFC31 3395A495 63763FAD 8A25AAB0 2CE8C0D9 2B3C0B36 C4FCBEE0 B56C0952 60F264BA B55F6C84 C0716294 510D644C 22A1CFB7 ABA77416 2F5C4789 0B9B9990 25B901DC EA838AB7 6DF1A602 3985142B 66BFACD0 17964990 3A2D2E18 E624247D B3E3D9BA C319197C 553E31D8 F3D75E65 8556A972 DC588FCB 1D4F7712 087241C1 9F535365 A59563B3 7E587186 F0A8B7F8 27104D45 3CEA7A18 C9469FF4 A8C92621 FCAD85CE 1053A568 8BF0F5EC 3581208F 5F40FB99 E1997B76 3055ABDF 490937FC FDB10EBE 30DB293B 96B8F948 51D1395F 711FA945 D919499E 7146936E F17A5166 C0FF39DF 04748203 F3E0CD0A 2AEB73D0 EBE40BC5
$U$	0x5FC6F7AB D3978738 A06742E5 75B3CDFF 7BDA7C91 5336F771 A7C46FD2 9A87B0FE E0AA810A 48C6F11E 1D6A10B9 C5DA251A 3C49B831 517FF01B DCDE01F7 A7F8321E 1747DE98 F77DFF4B A5052CB9 51629AA0 52A6F3D8 73C1FEFF F9690E2D E94C4ACA 9D568E52 55AEAB51 E964FEB7 0D2A6875 D5CAAB7E 82A63305 97B602E8 ED33AD0E EF9A90E1 F188A8D3 C2E01CE9 0D6F65EA 9B2881C0 01994011 03B84B6C DB129ACD DAF2124F 0965CC33 42E95682 A5308C4C 58AAD1D2 A91439FB DFED8CCE EEEF2FE6 CFBF15BE F497F000 41D2F60C C8CF2E96 4CE82B30 902DF17D 6E125EFA 1C5BD841 E66147D3 8A1AB88A 61541542 5A133023 5554E980 95637068 5919DE2B 793A0D1D B8D99B84 F2253BD3 351AD8FD F715AFD1 6A43A533 CB01ECCB 41E532D1 7B4D72A4 5F00CCB1 27CE38A1 19866557 B877B29C BD921E95 78570525 170E50E2 A0A3E391 04F024AE D1192AA D0527A2 18FB9C1C B40C15D1 9B79DEE3 F1A241A6 409623B9 7CEE9008 5C8C8A50 5CD12879 C510C360 4CB4459B 181F373A 78520CC7 87FD767C 1FD4C6B6 6249CE55 6691633A 7DFB3C3F BBD56DA4 FD489DF9 CB05631E F6293B4B 30DCDED5 8BBE87A8 AB0542EB AFF05ECC F7A8000F 273E3DD7 66D57C61 77296749 EAA49BDD 00B4F8F4 B1A6B0CF 0120DA9E 6FADCB8A 8D87A849 2E5613B8 AE8B1D7C 0F168027 BD6CD0EF 74A47FBD 7C91C0DB E2FC5F25 1F517BE1 353FD0BE 1C1EDABC 1D067DAC 8EFEB536 DEEF9DD6 23CD4CCF 57A60697 EC3716DB C244D8E1 F89BF6D3 B00915A0 7B3286EA C8AB79AC 35B96F5E CC6D7172 41296197 DB61BF78 3DC6DB48 2D8AAD43 9B31B6EB C6287817 010E571F 47A8D947 CFA160DE 398EDDD5 AAA6C489 5A7B0B95 6F962A9D 6629E8AB 5A1747FD 805A7A95 05BC2661 93EDD35B 1CF82140 FCD53A05 341B9B74 A7321895 86D409D2 B248D1A8 461DD94A 2BEAEB88 48F2DBE4 D42BE0BE 601B516F DCA03DE3 C69C17BB 13B6914A 7CBAC4AF B66160B0 9AB06327 545B8C6D 9838C036 0A9E2EED 056376AC 778221A8 C83D5813 D3780DF9 F425E2D1 9A83DDE9 426CE764 3206166C B476D23A 82BD2050 94A3BBE6 860F51D2 01D4CB68
名称	数值
$A 1$	0x86AC816C A208E159 A6C15DEC 985F2B39 32F7491B AA67C602 47F24157 9E99229 470CC3A7 6759065D E14D01F8 79CC50A6 CF8AE298 1149D2C9 39E936B1 0AA5FB4D 4CE18790 4918028D B81D1B08 16A1F57F 6B20E02B 8A8113A0 2C464291 18137CBD 58B857B7 F4CC016B 1D66C6D7 CD77BBF4 8FF25C0E 74DFE992 719D2F5 E20390FD BF5173D4 BAB558C7 308687EE 13275A36 13B06231 6878C5BE 8F2147C8 D54D60D3 E1B3D200 58896D9D 46A89FA6 A8ED8759 E2F69C21 74AE840A 73717A46 F8032E67 50691098 73EB53C0 0C979D84 C73428FF 9979852B 042433D2 AD90A0E6 4A87E3F6 BA8AF0ED F89D224C 2CEBBD42 726201AC 26A5B1D2 015A5D3E 2112CAC ACC9104 7AEEB973 ACE66A96 6FE3CD60 1D2D36C1 9AE31AA4 EEF751A 74C1855B E4C30D31 6B8DB258 3960AC01 E6F1AFBA FA400309 B8DACA2D 5F1D69B 73A79B1 6A344384 CDD69C88 AFB7B32B 949BE578 74A4C71D 75F48C35 1EC68F31 8A22FE86 D59AB0DD 2ECF14DF 67341921 61C3DD3C 3B78E830 FEA2B76 CBC5F168 3E474E8B 0C9021AB D3FC
$X A$	0x87AE326D 95367438 F5601AD2 8961E264 87730841 3952EA1C DC742402 7EEDC8AD
$X U$	0xD71CE05B F55FA8D9 7B26C1A2 374EB24F 7D173A5C B4031776 1827982C 20D7A85 37640DCB D1574716 163CB7C7 4DF3C271 09B1AB20 0F837E5E 913C0CBD 5BE4B4AC AF342C44 9EB60B04 7E8FD56C 5D854186 F012A17C 338CFA2D 56B3AD4 45465B04 0ACB9690 9AC59B2B FDA1448C 5EA069E0 5056E57D 62E2FE51 F36E68E8 060DFD97
$X K$	0xD0A9
$u$	0xD71CE05B F55FA8D9 7B26C1A2 374EB24F 7D173A5C B4031776 1827982C A20D7A85 37640DCB D1574716 163CB7C7 4DF3C271 09B1AB20 0F837E5E 13C0CBD 5BE4B4AC AF342C44 9EB60B047E8FD56C 5D854186 F012A17C 338CFA2D B56B3AD4 45465B04 0ACB9690 9AC59B2B FDA1448C 5EA069E0 5056E57D 62E2FE51 F36E68E8 060DFD96

表5 N为合数时的实验参数及结果

Table 5 Experimental parameters and results while N is composite

名称	数值
$L$	0xB95DE788 E63A90C9 A5E9DEEF 5B0FAECB 1961D18E 58CFBACC DAE90596 457702CB 4D221FAF CDFC4081 5C441225 ADF36468 BAAB2590 7CA49D3C 8DC1AC97 97911179 DDF67911 5304D649 1B794894 3F6F2C76 17B90055 040AE021 8C70F859 C61DDB2A 16A0996E 8EB96FB2 0E20C388 A6A9FA1A 10690DF9 6212D7A3 C7C2D11F C80E9DE8 69CC2589 23FF5408 6AD49D60 2538DB62 CEAD6375 2CDF252F C5B88B34 AF2173E3 0A618BEC 2158BA97 682A9C99 3FBF0180 23378C0C D8EA2996 6ECF23F1 28751D1F 9181FF87 9D99C199 EBF7BC95 B020460A B0328CBC 797FB429 43ACFD6C D6068C87 CF345E1E 2239FF1A 532A364F E3977637 14476173 C598766D 56945F61 3497DF01 B83652A6 EF59EB90 165DA127 82DC369C 2ED4BE53 747AA583 1371676B F18CEEC8 1F6F5AE7 EF75656F 8D5A49A7 46BDF136 474972B1 815F930C 55986E3D C4D113AE EEC08FBC 15F5F63C FDA2BB52 7DA6534F EDC4A45F 01301DAA D95BD794 BBA9BD26 EB09EF3C 6D6F8F35 9D338DFC 59AC56C2 0E95B660 AB52FC19 4E9980A3 335EF915 2F250066 CC51DE49 7F781C91 DC9A453D 3DD245C8 6BFEDACE 22FB1DD6 5C58E12C 17BB169F C50C3F73 EB0BEA83 A53CBFB8 4E8667E6 D0403CE4 35B37F6A 47CE5A33 1DA0DFF8 4C05F3C4 69541B3C 46D4D062 499C0C73 42B87611 CC56FDC5 23EB724B 39419D6E EB22F142 CF1EA13A A2D84435 573C564D 4D67725C 779B9708 408A9F70 52225D36 FB24642D 1DF297A0 C1C31952 668070C0 C97D97A3 0E1B2740 CF3943FC 7CAD1BC4 2D130DE2 57B31889 34983779 0A4865F2 A5EF3F6E 8F9273B3 4B9BBA2D
$U$	0x72C10C71 160F1A78 F2928B99 FAF8B277 F5FAE527 969CA911 FC642E94 CA117C15 EADDD11F E3C0F506 6589095F 6AA90772 290F6BB3 AC0BC130 415B0662 553809D0 D8DCD942 DA9E006C 61483AAC 69FCE190 22BF6D00 A9BCCDEA 6028D270 6003A6DF C975BBA1 A972CCD2 8EB9F918 1FBFAC09 957E5FD1 46D21E23 C14DCE2F 3C86DEFC 46628BCD 0FE6B666 BC691297 54BAC344 5E7174A3 45B31F6F 5B0B6F7F 19A0D0BF 6EEA4413 F92AAE0C 695A7005 F468EC49 2069E04C C659D8DF 853F75A9 DFC38FDD 2EB5323C 12387507 35A9815F 94129124 B3EC051E 891422AE B27F6FF6 CEE85C50 08742C57 D47BE74C C247E472 D32EA652 8F2B9FA4 6E36903C F946F4E4 2FAF785D 7E6CD6C5 ACB9E4D2 515F63BC 5E617F7A 6AE423AB CF9B883F 2CF0DD30 D3ED1C43 2B326AE7 41D44A96 F114D803 6BEEB5A4 23E2B2AF 10A366BE A4515226 16D16332 5511EEAA DC1F4726 B00DD6E8 AF3D09EC 7FC7F413 FBB9AA87 29FA5D6C 9E7B4465 9F017427 9A6389E6 D335EF64 45EF330E 79F3F5D8 770C84AF C46A408D 4F45B277 658EEC37 88056CD6 65707B84 02D07034 A55CBE05 EE8E5A88 4B930B90 29B9C7B5 4771E0FC D756FF18 9402DD5E 299D2845 2C78FF0D 85101937 E4A45936 D000F055 DEFFA827 357C117E B1988642 2FD692A3 FED86571 50C6C26D AE352543 2D770322 836D6F35 CC9B44C4 D5C9CFE0 3CE52F12 AF9D5B9D 642BD0AE 3C65A778 CECD0B5E 850D00A7 831B2020 2D94CFEA 1B0AF9C2 40221EEF B638B121 1DBB34B1 8A43E580 0824C702 9DD90B5F ECDF5421 E36A105C C2082DF9 D9D1B496 B0B03CCA 3EB34004
$u$	0xF56D7E1C 8880F5D3 44FDE7B8 A07A4844 4E0407AA CA05B7C7 8C33AA8B B7F36363 75BB1497 F13CD439 565683B3 ABEF8FFE 7F74801A 5DC1A929 F453B9C9 F2DA8F02 DA624F5E 0BCDA365 8CA04AD9 8E8DB1AE E60FBDD6 6E000151 ACB89F9D 0207DA70 7EB8F3F8 0B1EA00C 8AFD6A76 33311708 2943A693 4FF68667 997EB823 17AA9A28 8BC1F0A6 128CBA90 E8C9EA56 969C5F13 33A0E89F D8CC0522 33D1BE84 124786C4 3D42A36E 18254FD2 177B93DA 08D7FAEE F7CD8EE6 5CD8FEA6 CF5302DB DEE2CB79 E3F8E855 30EB2FCA 123C0327 133A59DA D540ABAE 57DE0F0B 4C629CB7 EC8EB886 79C7DC39 4D6ACC88 EB0C482A 7A1AA619 B180BFBA 955A23D7 FDF60410 4C6B9046

表5 N为合数时的实验参数及结果

Table 5 Experimental parameters and results while N is composite

名称	数值
$L$	0xB95DE788 E63A90C9 A5E9DEEF 5B0FAECB 1961D18E 58CFBACC DAE90596 457702CB 4D221FAF CDFC4081 5C441225 ADF36468 BAAB2590 7CA49D3C 8DC1AC97 97911179 DDF67911 5304D649 1B794894 3F6F2C76 17B90055 040AE021 8C70F859 C61DDB2A 16A0996E 8EB96FB2 0E20C388 A6A9FA1A 10690DF9 6212D7A3 C7C2D11F C80E9DE8 69CC2589 23FF5408 6AD49D60 2538DB62 CEAD6375 2CDF252F C5B88B34 AF2173E3 0A618BEC 2158BA97 682A9C99 3FBF0180 23378C0C D8EA2996 6ECF23F1 28751D1F 9181FF87 9D99C199 EBF7BC95 B020460A B0328CBC 797FB429 43ACFD6C D6068C87 CF345E1E 2239FF1A 532A364F E3977637 14476173 C598766D 56945F61 3497DF01 B83652A6 EF59EB90 165DA127 82DC369C 2ED4BE53 747AA583 1371676B F18CEEC8 1F6F5AE7 EF75656F 8D5A49A7 46BDF136 474972B1 815F930C 55986E3D C4D113AE EEC08FBC 15F5F63C FDA2BB52 7DA6534F EDC4A45F 01301DAA D95BD794 BBA9BD26 EB09EF3C 6D6F8F35 9D338DFC 59AC56C2 0E95B660 AB52FC19 4E9980A3 335EF915 2F250066 CC51DE49 7F781C91 DC9A453D 3DD245C8 6BFEDACE 22FB1DD6 5C58E12C 17BB169F C50C3F73 EB0BEA83 A53CBFB8 4E8667E6 D0403CE4 35B37F6A 47CE5A33 1DA0DFF8 4C05F3C4 69541B3C 46D4D062 499C0C73 42B87611 CC56FDC5 23EB724B 39419D6E EB22F142 CF1EA13A A2D84435 573C564D 4D67725C 779B9708 408A9F70 52225D36 FB24642D 1DF297A0 C1C31952 668070C0 C97D97A3 0E1B2740 CF3943FC 7CAD1BC4 2D130DE2 57B31889 34983779 0A4865F2 A5EF3F6E 8F9273B3 4B9BBA2D
$U$	0x72C10C71 160F1A78 F2928B99 FAF8B277 F5FAE527 969CA911 FC642E94 CA117C15 EADDD11F E3C0F506 6589095F 6AA90772 290F6BB3 AC0BC130 415B0662 553809D0 D8DCD942 DA9E006C 61483AAC 69FCE190 22BF6D00 A9BCCDEA 6028D270 6003A6DF C975BBA1 A972CCD2 8EB9F918 1FBFAC09 957E5FD1 46D21E23 C14DCE2F 3C86DEFC 46628BCD 0FE6B666 BC691297 54BAC344 5E7174A3 45B31F6F 5B0B6F7F 19A0D0BF 6EEA4413 F92AAE0C 695A7005 F468EC49 2069E04C C659D8DF 853F75A9 DFC38FDD 2EB5323C 12387507 35A9815F 94129124 B3EC051E 891422AE B27F6FF6 CEE85C50 08742C57 D47BE74C C247E472 D32EA652 8F2B9FA4 6E36903C F946F4E4 2FAF785D 7E6CD6C5 ACB9E4D2 515F63BC 5E617F7A 6AE423AB CF9B883F 2CF0DD30 D3ED1C43 2B326AE7 41D44A96 F114D803 6BEEB5A4 23E2B2AF 10A366BE A4515226 16D16332 5511EEAA DC1F4726 B00DD6E8 AF3D09EC 7FC7F413 FBB9AA87 29FA5D6C 9E7B4465 9F017427 9A6389E6 D335EF64 45EF330E 79F3F5D8 770C84AF C46A408D 4F45B277 658EEC37 88056CD6 65707B84 02D07034 A55CBE05 EE8E5A88 4B930B90 29B9C7B5 4771E0FC D756FF18 9402DD5E 299D2845 2C78FF0D 85101937 E4A45936 D000F055 DEFFA827 357C117E B1988642 2FD692A3 FED86571 50C6C26D AE352543 2D770322 836D6F35 CC9B44C4 D5C9CFE0 3CE52F12 AF9D5B9D 642BD0AE 3C65A778 CECD0B5E 850D00A7 831B2020 2D94CFEA 1B0AF9C2 40221EEF B638B121 1DBB34B1 8A43E580 0824C702 9DD90B5F ECDF5421 E36A105C C2082DF9 D9D1B496 B0B03CCA 3EB34004
$u$	0xF56D7E1C 8880F5D3 44FDE7B8 A07A4844 4E0407AA CA05B7C7 8C33AA8B B7F36363 75BB1497 F13CD439 565683B3 ABEF8FFE 7F74801A 5DC1A929 F453B9C9 F2DA8F02 DA624F5E 0BCDA365 8CA04AD9 8E8DB1AE E60FBDD6 6E000151 ACB89F9D 0207DA70 7EB8F3F8 0B1EA00C 8AFD6A76 33311708 2943A693 4FF68667 997EB823 17AA9A28 8BC1F0A6 128CBA90 E8C9EA56 969C5F13 33A0E89F D8CC0522 33D1BE84 124786C4 3D42A36E 18254FD2 177B93DA 08D7FAEE F7CD8EE6 5CD8FEA6 CF5302DB DEE2CB79 E3F8E855 30EB2FCA 123C0327 133A59DA D540ABAE 57DE0F0B 4C629CB7 EC8EB886 79C7DC39 4D6ACC88 EB0C482A 7A1AA619 B180BFBA 955A23D7 FDF60410 4C6B9046

参考文献 24

[1]	MORIARTY K M, KALISKI B, JONSSON J, et al. PKCS #1: RSA cryptography specifications version 2.2[J]. Internet Engineering Task Force, Request for Comments, 2016, 8017: 1-78.
[2]	KERRY C F, GALLAGHER P D. Digital signature standard (DSS)[R]. Federal Information Processing Standards, 2013.
[3]	HOHENBERGER S, LYSYANSKAYA A. How to securely outsource cryptographic computations[C]// LNCS 3378: Proceedings of the 2nd Conference on Theory of Cryptography, Cambridge, Feb 10-12, 2005. Berlin, Heidelberg: Springer, 2005: 264-282.
[4]	CHEN X, LI J, MA J, et al. New algorithms for secure outsourcing of modular exponentiations[J]. IEEE Transactions on Parallel and Distributed Systems, 2013, 25(9): 2386-2396. DOI URL
[5]	YE J, XU Z, DING Y. Secure outsourcing of modular exponentiations in cloud and cluster computing[J]. Cluster Computing, 2016, 19(2): 811-820. DOI URL
[6]	FU S, YU Y, XU M. A New efficient algorithm for secure outsourcing of modular exponentiations[J]. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2020, 103(1): 221-224.
[7]	VAN DIJK M, CLARKE D, GASSEND B, et al. Speeding up exponentiation using an untrusted computational resource[J]. Designs, Codes and Cryptography, 2006, 39(2): 253-273. DOI URL
[8]	WANG Y, WU Q, WONG D S, et al. Securely outsourcing exponentiations with single untrusted program for cloud sto-rage[C]// Proceedings of the 19th European Symposium on Research in Computer Security, Wroclaw, Sep 7-11, 2014. Cham: Springer, 2014: 326-343.
[9]	CHEVALIER C, LAGUILLAUMIE F, VERGNAUD D. Privately outsourcing exponentiation to a single server: cryptanalysis and optimal constructions[J]. Algorithmica, 2021, 83(1): 72-115. DOI URL
[10]	DING Y, XU Z, YE J, et al. Secure outsourcing of modular exponentiations under single untrusted programme model[J]. Journal of Computer and System Sciences, 2017, 90: 1-13. DOI URL
[11]	LI S, HUANG L, FU A, et al. CExp: secure and verifiable outsourcing of composite modular exponentiation with single untrusted server[J]. Digital Communications and Networks, 2017, 3(4): 236-241. DOI URL
[12]	FU A, LI S, YU S, et al. Privacy-preserving composite modular exponentiation outsourcing with optimal checkability in single untrusted cloud server[J]. Journal of Network and Computer Applications, 2018, 118: 102-112. DOI URL
[13]	RANGASAMY J, KUPPUSAMY L. Revisiting single-server algorithms for outsourcing modular exponentiation[C]// LNCS 11356:Proceedings of the 19th International Conference on Cryptology in India, New Delhi, Dec 9-12, 2018. Cham: Springer, 2018: 3-20.
[14]	ZHOU K, AFIFI M H, REN J. ExpSOS: secure and verifiable outsourcing of exponentiation operations for mobile cloud computing[J]. IEEE Transactions on Information Forensics and Security, 2017, 12(11): 2518-2531. DOI URL
[15]	KANNAN R. Algorithmic geometry of numbers[J]. Annual Review of Computer Science, 1987, 2(1): 231-267. DOI URL
[16]	AJTAI M. Generating hard instances of lattice problems[C]// Proceedings of the 28th Annual ACM Symposium on the Theory of Computing, Philadelphia, May 22-24, 1996. New York: ACM, 1996: 99-108.
[17]	BONEH D. Twenty years of attacks on the RSA cryptosystem[J]. Notices of the AMS, 1999, 46(2): 203-213.
[18]	REGEV O. On lattices, learning with errors, random linear codes, and cryptography[J]. Journal of the ACM, 2009, 56(6): 1-40.
[19]	MINKOWSKI H. Geometrie der Zahlen[J]. Monatsh. f. Mathematik und Physik, 1910, 22: A30.
[20]	LENSTRA A K, LENSTRA H W, LOVÁSZ L. Factoring polynomials with rational coefficients[J]. Mathematische Annalen, 1982, 261: 515-534. DOI URL
[21]	MAY A. New RSA vulnerabilities using lattice reduction methods[D]. Paderborn: University of Paderborn, 2003.
[22]	HOWGRAVE-GRAHAM N. Finding small roots of univariate modular equations revisited[C]// LNCS 1355: Proceedings of the 6th International Conference on Cryptography and Coding, Cirencester, Dec 17-19, 1997. Berlin, Heidelberg: Springer, 1997: 131-142.
[23]	HOWGRAVE-GRAHAM N. Approximate integer common divisors[C]// LNCS 2146: Proceedings of the International Conference on Cryptography and Lattices, Providence, Mar 29-30, 2001. Berlin, Heidelberg: Springer, 2001: 51-66.
[24]	HERRMANN M, MAY A. Solving linear equations modulo divisors:on factoring given any bits[C]// LNCS 5350: Proceedings of the 14th International Conference on the Theory and Application of Cryptology and Information Security, Melbourne, Dec 7-11, 2008. Berlin, Heidelberg: Springer, 2008: 406-424.

模指数外包方案ExpSOS的格基密码分析

Lattice-Based Cryptanalysis on Outsourcing Scheme of Modular Exponentiations ExpSOS

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 5

参考文献 24

相关文章 1

编辑推荐

Metrics