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

• 网络与信息安全 • 上一篇    下一篇

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

郑云海1, 田呈亮1,2,+()   

  1. 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 Yunhai1, TIAN Chengliang1,2,+()   

  1. 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)

摘要:

随着云计算的普及,外包计算作为一种重要的云服务形式,日益引起学术界与工业界的广泛关注。模指数操作作为一种耗时的基本密码运算广泛地应用于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

中图分类号: