Skip to main content

铜锁再次参与开源之夏

· 7 min read
Paul Yang
PMC Member of Tongsuo
Xudong Guo
Maintainer of Tongsuo

🎉 开源之夏2024 🌐 铜锁密码学社区项目现已开放报名!加入我们,一起探索开源软件的无限可能! 在本年度开源之夏活动中,铜锁开源社区共发布了2个项目,涵盖 Golang、C 和 Rust 语言的开发工作,目前正在火热报名中。可以登录开源之夏官网获取项目详细信息:

🔗 开源之夏官网https://summer-ospp.ac.cn/
🔗 开源之夏2024铜锁项目列表https://summer-ospp.ac.cn/org/orgdetail/e4de262f-50b1-4f11-930b-8b8e841de420?lang=zh

什么是开源之夏

📚 开源之夏 是由中国科学院软件研究所“开源软件供应链点亮计划”发起并长期支持的一项暑期开源活动,旨在鼓励在校学生积极参与开源软件的开发维护,培养和发掘更多优秀的开发者,促进优秀开源软件社区的蓬勃发展,助力开源软件供应链建设。 开源之夏联合国内外开源社区,针对重要开源软件的开发与维护提供项目任务,面向全球高校学生开放报名,中选学生将在项目资深开发者(项目导师)的指导下,参与开源贡献,完成开发工作并贡献给开源社区

什么是铜锁

铜锁,全称开放原子铜锁(OpenAtom Tongsuo),是一个关于密码学和数据安全的开源社区,拥有多个密码学开源项目,包括铜锁密码学算法库、铜锁密码库嵌入式版和 RustyVault 机密信息管理软件。铜锁诞生于蚂蚁集团,于2023年完成了向开放原子开源基金会的捐赠,目前是开放原子开源基金会的孵化期项目。铜锁当前由其PMC进行管理,已广泛的应用在互联网、金融、司法、电信等诸多领域中,为存储、网络、密钥管理、隐私计算、区块链、IoT 等诸多业务场景提供底层的密码学基础能力。

社区项目主仓库https://github.com/Tongsuo-Project
开源协议:Apache-2.0
技术领域:密码学、SSL/TLS、PKI、数据安全、密钥管理
编程语言C Java Go Python Rust

开源之夏 2024 之铜锁项目

铜锁密码学开源社区自2023年起参与开源之夏活动,并取得了显著成效,不仅促进了社区的发展,还培养了在校学生的实践能力。2024年,铜锁密码学开源社区再次参与,并发布了两个项目:

一、铜锁密码库 Go 语言 SDK 国密算法和协议开发

Tongsuo-Go-SDK 是铜锁开源社区基于铜锁密码库项目提供的 Golang SDK,目标是为 Golang 开发者提供国密算法和安全传输协议等功能。Tongsuo-Go-SDK 项目已经提供了部分国密算法和安全传输协议功能,需要继续完善。

项目导师:K1
项目编号:24e4d0074
导师邮箱dongbeiouba@gmail.com
编程语言:Golang,C
技术领域:密码学、PKI、SSL/TLS、网络安全、数据安全
项目成果仓库https://github.com/Tongsuo-Project/tongsuo-go-sdk
项目主页https://summer-ospp.ac.cn/org/prodetail/24e4d0074
项目技术要求

  1. 熟悉Golang编程语言开发
  2. 有密码学基础,了解常见密码学算法和协议
  3. 了解开源项目开发流程

希望实现的功能包括

  • SM2加解密
  • 国密证书签发(双证书)
  • TLCP功能完善,包括 SNI、ALPN 和 Session 复用等
  • TLS 1.3 + 商密套件
  • 跨平台支持,以上所有功能需要支持 Linux、MacOS 和 Windows 系统

二、铜锁社区项目 RustyVault 支持 prometheus 日志开发

RustyVault 是铜锁开源社区的生态项目,目标是成为一个完全可控和安全可靠的高性能密钥管理开源软件,已经提供了密钥管理的基础功能,还需要继续完善。

项目导师:金九
导师邮箱wanyco@gmail.com
编程语言:Rust
技术领域:密码学、云原生、Prometheus、Hashicorp Vault、审计
项目成果仓库https://github.com/Tongsuo-Project/RustyVault
项目主页https://summer-ospp.ac.cn/org/prodetail/24e4d0375
项目技术要求

  1. 熟悉 Rust 编程语言开发和 prometheus 日志原理
  2. 有密码学基础,熟悉密钥管理,了解常见密码学算法和协议
  3. 了解开源项目开发流程

希望实现的功能包括

  • 支持 prometheus 日志

重要日期提醒

以下是您需要关注的关键时间节点,确保不错过任何重要机会!

  • 📅 学生报名、导师沟通和项目申请: 04/30 - 06/04
  • 🔍 项目申请审核: 06/05 - 06/25
  • 📢 入选学生项目公布: 06/26

本次铜锁密码学开源社区发布的两个项目,涉及商用密码算法和协议、Rust 语言、云原生体系支持等前沿领域。我们诚挚邀请所有对这些领域感兴趣的开发者前往开源之夏官网获取更多信息。

🌟 铜锁密码学开源社区 期待您的加入,让我们携手推动开源软件的发展,为构建一个更加安全、开放的软件生态贡献我们的力量!

铜锁开源社区管理制度

· 13 min read
Paul Yang
PMC Member of Tongsuo

第一章 总则

第一条 社区名称

铜锁开源社区是归属于开放原子开源基金会的开源项目群。铜锁开源社区中包含有多个开源项目。铜锁开源社区的中文全称为开放原子铜锁,简称铜锁;英文全称为OpenAtom Tongsuo,简称为Tongsuo;Logo为: image.png

第二条 使命和愿景

愿景:成为中国乃至全球最具影响力的密码学基础设施开源社区

使命:基于持续的技术创新,为用户提供先进的密码学技术能力、数据安全能力和监管合规能力

第三条 业务范围

  1. 以密码学算法库为基础,建设密码学基础设施软件,并对市场提供开源供给;
  2. 探索和构建密码行业软件开原生态,促进密码学技术以及相关产业发展;
  3. 支持第三方厂商基于本社区中开源项目的商业化行为。

第二章 社区结构

第四条 社区角色定义

铜锁开源社区的核心是社区中的人。这些不同角色的人们形成了社区的基础、推动了社区的发展、也定义了社区的未来。因此需要对角色进行清晰的定义,并明确其对应的权利和责任。

总体来看,铜锁开源社区中的角色可以划分为“用户”、“维护人”以及“项目管理委员会”。

用户

用户是指下载、编译、安装或使用铜锁开源社区中各开源项目的组织或个人。用户使用铜锁开源社区中各开源项目的方式需要符合各项目“开源许可证”的规定。

用户可以向铜锁开源社区报告bug、提交问题、请求新特性开发、请求帮助和技术支持等,但需要通过铜锁项目管理委员会指定的渠道和方式。同时由于开源项目的特殊性,铜锁项目管理委员会不对上述行为做得到必然回应的承诺。

维护人

维护人是指一些拥有特定铜锁开源项目代码仓库或文档仓库相关权限的技术人员,这里的权限一般指向代码仓库提交代码、评审代码合入请求、文档的创建和编写等。即维护人需要对铜锁各项目以及其相关代码仓库或文档的维护负责,并确保来自铜锁社区的贡献(代码或文档等)与项目利益是一致的。

维护人资格执行邀请制。即按铜锁项目管理委员会流程,经过委员会批准后,赋予维护人相关代码或文档维护权限。同时,铜锁项目管理委员会经合法流程,也可以撤销维护人的代码或文档维护权限。

维护人须认同铜锁开源社区的使命和愿景,并对铜锁开源社区做出技术上的贡献。铜锁开源社区对其维护人进行贡献度的考核,贡献度考核标准为:每个自然季度中,至少提交或评审一次代码合并请求。

项目管理委员会

铜锁项目管理委员会,即Tongsuo Project Management Committee,以下简称为“铜锁PMC”,是铜锁开源社区的最高决策机构,也是代表铜锁对外发声的唯一官方机构。铜锁PMC由个人或组织组成,具体分为:

  1. 代表企业参加铜锁PMC
    1. 需要所在企业的授权书(盖章)
    2. 更换企业代表时需要该企业重新出具授权书
    3. 当企业委派代表出现变化时,如果该企业 3 个月内没有指派新代表,则认为该企业自动放弃 PMC 资格
  2. 代表个人参加铜锁PMC
    1. 个人代表参与 PMC 工作的,需现有成员推荐并获得超过80%的PMC成员认可,方可加入

无论个人PMC还是企业/组织PMC代表均需要按照规定的工作流程,行使其权利并承担相应的责任。

铜锁PMC的工作流程、权利和责任,由本制度的第五条《项目管理委员会的权利和责任》具体制定。

第三章 社区角色的责任和权利

第五条 项目管理委员会的责任和权利

铜锁PMC代表铜锁开源社区的官方声音,并以投票制做为基本的工作方式。铜锁PMC的主要责任和权利有:

  • 需要为铜锁社区带来持续且实际的价值贡献,包括(满足之一即可):
    • 直接资金的捐赠,不少于人民币叁万元/年
    • 投入不少于1个铜锁维护者/年的研发资源用于社区项目的研发、维护工作
    • 实现铜锁在某行业的重大应用和落地
  • 制定项目的战略方向,具体包括:
    • 资金募集
    • 对外关系和生态规划
    • 功能特性规划
    • 里程碑和优先级规划
    • 版本生命周期管理
  • 制定和维护社区的管理制度
  • 管理铜锁PMC成员资格的准入和退出
  • 管理铜锁维护人资格的准入和退出
  • 管理并审计社区的财务
  • 负责社区中项目的法律合规
  • 每个自然年度PMC需要出轮值秘书,负责各类例行工作的组织。其中个人PMC和技术成员不受此约束
  • PMC成员需履行参与投票进行决策的责任,1个自然年内3次不参加表决,则取消PMC资格
  • PMC成员需按要求出席线上例会以及线下例会,连续3次不出席者,取消PMC资格
    • 特殊情况可以请假或委托他人代为参与

第六条 项目管理委员会的工作流程

铜锁PMC采用投票表决行使其权利。投票表决的事项包括但不限于:

  • 关于铜锁PMC成员资格的变化
  • 关于铜锁维护人资格的变化
  • 关于铜锁开源社区管理制度的变更
  • 其他铜锁PMC成员认为有必要决策的事项

铜锁PMC的投票表决事项由铜锁PMC成员发起。合法的投票选项有:

  • 同意
  • 不同意
  • 弃权

每个投票均须不少于70%的PMC成员参与,且有效参与中“同意”票数超过90%则视为表决通过。

每个投票均需要设置投票期限,超期则视为投票无效。

投票可以利用线下会议机会、也可以利用线上工具如钉钉、微信等进行。

铜锁PMC召开月度线上例会,并每个自然季度举办一次线下会议,具体有:

  • 线上例会主要内容
    • 讨论本月需要决策的事项
    • 同步和讨论本月内铜锁开源社区的重要进展,包括研发进展、业务进展等
  • 线下例会主要内容
    • 针对本季度铜锁开源社区各领域工作进行总结
    • 讨论和确定下个季度的工作方向和重点
  • 下上和线下例会的组织,应由年度轮值PMC所出秘书负责

除例会外,铜锁PMC成员可以随时召集发起其认为有必要的会议主题。

铜锁PMC使用独立的知识库系统跟踪和记录会议纪要、投票决议等信息。铜锁PMC所使用的知识库默认不对公众公开。

第七条 铜锁维护人的责任和权利

铜锁维护人团队负责所有和技术相关的决策和管理事项,包括:

  • 需求分析
  • 架构设计
  • 代码实现
  • 测试用例编写
  • 文档编写
  • 代码评审
  • 铜锁基础设施(网站、各类工具等)维护
  • 向铜锁PMC建议新的维护人资格

铜锁维护人资格一般由铜锁PMC成员提名并经过投票表决通过生效,铜锁维护人根据职责范围以及其工作的方向,对铜锁社区中的1个或多个代码仓库拥有写权限。

铜锁维护人需要持续的对铜锁社区的相关开源项目做出贡献,否则其维护人资格经由铜锁PMC决议后,可能会被移除。被认可的工作贡献包括:

  • 每个季度至少1次的代码提交,或
  • 每个季度至少1次的代码评审,或
  • 每个季度通过铜锁规定的渠道进行至少1次的社区答疑或互动

第八条 铜锁开源社区开源项目代码准入要求

铜锁开源社区中存在多个密码学或安全相关的开源项目,因此如何确保项目高水平的代码质量是我们关心的重点。为此,铜锁PMC制定了代码准入要求如下:

  • 每个代码合入请求(Pull Request)需要经过至少2个铜锁维护人的代码评审并均处同意意见;
  • 如代码合入请求由铜锁维护人发起,则只需要再经过1个铜锁维护人的评审并处同意意见即可;
  • 合入的代码需要有对应的测试用例
  • 合入的代码需要有完善的文档(如API或使用教程)

铜锁维护人应当严格遵守并执行上述代码准入要求,并对自己拥有写权限的代码仓库的最终软件质量负责。

第四章 社区财务制度、法务合规和运营管理

铜锁密码学开源社区的财务、法务和运营管理制度遵从开放原子开源基金会的相关管理要求。

关于性能的一些数据

· 3 min read
Paul Yang
PMC Member of Tongsuo

选择版本:铜锁master,铜锁8.3,OpenSSL 3.0

性能指标:SM2加解密、签名验签、密钥生成、SM3哈希、SM4的ECB和CBC模式加解密

测试数据大小:1MB 的随机数据

测试环境:macOS 11.7 / 2.4 GHz Quad-Core Intel Core i5 / 16 GB 2133 MHz LPDDR3

测试程序:master/examples目录下的方式进行测试(见:Tongsuo/examples/perf at master · Tongsuo-Project/Tongsuo),单进程测试

铜锁 master铜锁8.3OpenSSL 3.0
sm2-enc: 285 Mbpssm2-enc: 281 Mbpssm2-enc: 282 Mbps
sm2-dec: 291 Mbpssm2-dec: 289 Mbpssm2-dec: 296 Mbps
sm2-sign: 2506/ssm2-sign: 2364/ssm2-sign: 2484/s
sm2-verify: 2772/ssm2-verify: 2673/ssm2-verify: 2810/s
sm2-keygen: 1973/ssm2-keygen: 2038/ssm2-keygen: 1968/s
sm3-hash: 1863 Mbpssm3-hash: 1826 Mbpssm3-hash: 1908 Mbps
sm4-ecb-enc: 908 Mbpssm4-ecb-enc: 906 Mbpssm4-ecb-enc: 902 Mbps
sm4-cbc-enc: 864 Mbpssm4-cbc-enc: 855 Mbpssm4-cbc-enc: 854 Mbps
sm4-ecb-dec: 919 Mbpssm4-ecb-dec: 913 Mbpssm4-ecb-dec: 905 Mbps
sm4-cbc-dec: 921 Mbpssm4-cbc-dec: 915 Mbpssm4-cbc-dec: 917 Mbps

【附录:基于apps/speed的部分测试】

SM4-CBC
铜锁master:
The 'numbers' are in 1000s of bytes per second processed.
type 16 bytes 64 bytes 256 bytes 1024 bytes 8192 bytes 16384 bytes
sm4 113645.27k 114115.80k 115176.88k 114105.11k 113833.18k 112978.60k
tongsuo-8.3:
The 'numbers' are in 1000s of bytes per second processed.
type 16 bytes 64 bytes 256 bytes 1024 bytes 8192 bytes 16384 bytes
sm4 19246.65k 49904.77k 80437.00k 100238.64k 106778.20k 106173.78k
openssl-3.0:
The 'numbers' are in 1000s of bytes per second processed.
type 16 bytes 64 bytes 256 bytes 1024 bytes 8192 bytes 16384 bytes
SM4-CBC 105532.58k 110182.79k 109867.86k 111192.36k 110362.62k 110890.64k

SM2门限的性能数据

以下单位均为:次/秒

关闭SM2优化

普通SM2:

  • keygen:5069
  • 签名:5859
  • 验签:6154

SM2门限:

  • keygen:1850
  • 签名:4967
  • 验签:5019

开SM2优化

普通SM2:

  • keygen:22560
  • 签名:20327
  • 验签:11325

SM2门限:

  • keygen:5980
  • 签名:8031
  • 验签:8308

铜锁获2023开源创新榜“优秀开源项目

· 6 min read
Paul Yang
PMC Member of Tongsuo

tongsuo_cert.jpg 2023年12月15日,由中国科协科学技术传播中心中国计算机学会中国通信学会中国科学院软件研究所共同主办,CSDN 承办的 2023 开源创新榜专家评审会在国家科技传播中心成功举办。评委会主任、中国计算机学会开源发展委员会主任王怀民院士,评委会副主任、中国科协科学技术传播中心副主任陈锐,评委会副主任、中国通信学会副理事长兼秘书长张延川,评委会副主任、中国科学院软件研究所所长赵琛与来自全国学会、大学、科研院所、企业、开源基金会、行业联盟等二十多位开源专家共同参与了本届榜单评审工作,会议由陈锐主持。

2023 年开源创新榜相较往年有以下几个变化:

一是进一步提升权威性,主办单位新加入中国计算机学会、中国通信学会、中国科学院软件研究所,四家主办单位优势互补,共同推动榜单策划、征集申报、专家评审等工作重点。

二是进一步提升公信力,由王怀民院士担任评委会主任,指导组建了结构更加科学、领域更加全面的评审专家库,从中提名形成最终评审专家。

三是进一步提升专业度,围绕项目、社区、人物三大类别,四家主办单位打磨了更加客观、严谨、贴合实际的评审标准和更加开放、公平、科学的评审办法,在征集过程中公开标准细节,接受社会的意见反馈,形成良性循环。

评审委员会主任王怀民院士指出,人类文明和科技文明发展中,一项成果得以记录、传播、共享才对推动社会进步有价值,开源是群体智慧的现代表征,在当下推动高质量发展、高水平安全具有重要现实意义。通过开源创新榜征集评选工作,可以挖掘和推广我国在开源技术领域的优秀成果和先进经验,为一线科技工作者及其创新成果创造更多展示、交流、推广的机会,希望大家共同努力,将开源创新榜打造成为业界最最权威、最典型和最具影响力的标杆。

评委会最终评选出优秀开源项目 20 个,开放原子开源基金会旗下“孵化期”开源项目“铜锁开源密码学算法库”入选其中:

Screen Shot

铜锁(Tongsuo)是一个提供现代密码学算法和安全通信协议的开源基础密码库,为存储、网络、密钥管理、隐私计算等诸多业务场景提供底层的密码学基础能力,实现数据在传输、使用、存储等过程中的私密性、完整性和可认证性,为数据生命周期中的隐私和安全提供保护能力。

铜锁于2020年10月开源,已获得国家密码管理局商用密码检测中心颁发的商用密码产品认证证书,符合GM/T 0028《密码模块安全技术要求》的安全一级要求,助力用户在密改、密评、等保检查等过程中,更加严谨地满足商用密码技术合规的要求。 当前,铜锁开源项目已经由蚂蚁集团完成了向开放原子开源基金会的捐赠,成为基金会的“孵化期”项目,也是基金会唯一的密码学方向开源项目。在基金会孵化过程中,铜锁开源社区先后启动了“铜锁嵌入式版”和“RustyVault密钥管理系统”两个新项目的开发,已从单一开源项目发展为项目群。蚂蚁集团在铜锁完成捐赠后持续对项目进行投入,成立了铜锁项目管理委员会,引入多家领军企业参与铜锁开源项目的管理,推动铜锁进入到了独立发展的新阶段。

铜锁的商用密码产品认证证书

· One min read
Paul Yang
PMC Member of Tongsuo

本页面提供铜锁全部的商用密码产品认证证书(即俗称的国密资质)高清版本下载,铜锁的用户可以自由取用。

Android:BabaSSL移动端软件密码模块

证书编号:GM003312220220743

PDF格式: BabaSSL移动端软件密码模块.pdf

PNG格式 BabaSSL移动端软件密码模块.png

iOS:BabaSSL IOS端软件密码模块

证书编号:GM003312220230052

PDF格式: BabaSSL IOS端软件密码模块.pdf

PNG格式: Page 0001.png

Linux:应用安全软件密码模块(Linux版)

证书编号:GM003312220230044

PDF格式: 应用安全软件密码模块(Linux版).pdf

PNG格式: Page 0001.png

Tongsuo 支持半同态加密算法 Paillier

· 16 min read
Jin Jiu
Maintainer of Tongsuo

背景

《Tongsuo 支持半同态加密算法 EC-ElGamal》中,已经阐述了同态和半同态加密算法的背景和原理,可以移步查阅,总之,同态算法在隐私计算领域有着重要的作用,目前应用比较广泛的是 Paillier 和 EC-ElGamal 半同态加密算法,这两个算法都只支持加法同态,其接口也类似,只是原理和性能不一样,Paillier 是基于复合剩余类的困难性问题(大数分解难题)的公钥加密算法,有点类似 RSA,而 EC-ElGamal 是基于椭圆曲线数学理论的公钥加密算法,其安全性理论上要比 Paillier 要更好,但其性能各有优劣,EC-ElGamal 的加密和密文加法性能要比 Paillier 好,而 Paillier 的解密和密文标量乘法性能要比 EC-ElGamal 好,而且稳定,EC-ElGamal 的解密性能与解密的数字大小有关系,数字越大可能需要解密的时间越长,这与 EC-ElGamal 解密用到的解密表有关系,而 Paillier 的解密就没有这个问题,可以根据自己的业务特点选择使用 Paillier 还是 EC-ElGamal。

Paillier 原理

密钥生成

  1. 随机选择两个大素数 p,qp,q,满足 gcd(pq,(p1)(q1))=1gcd(pq, (p-1)(q-1))=1,且满足 p 和 q 的长度相等;
  2. 计算 n=pqn=pq以及λ=lcm(p1,q1)\lambda=lcm(p-1, q-1)lcmlcm 表示最小公倍数;
  3. 随机选择整数 gZn2g\gets \mathbb{Z}_{n^2}^*,一般gg的计算公式如下:
    1. 随机选择整数 kZnk \in \mathbb{Z}_{n}^*
    2. 计算:g=1+kng=1+kn,为了简化和提高性能,kk一般选1,g=1+ng=1+n
  4. 定义 L 函数:L(x)=x1nL(x)=\frac{x-1}{n},计算:μ=(L(gλ mod n2))1 mod n\mu=(L(g^\lambda \space mod \space n^2))^{-1} \space mod \space n
  5. 公钥:(n, g)(n, \space g),私钥:(λ, μ)(\lambda, \space \mu)

加密

  1. 明文 m,满足 n<m<n-n < m < n
  2. 选择随机数 r,满足 0r<n0 \leq r<nrZnr\in \mathbb{Z}_n^*
  3. 计算密文:c=gmrn mod n2c=g^mr^n\space mod\space n^2

解密

  1. 密文 c,满足 cZn2c\in \mathbb{Z}_{n^2}^*
  2. 计算明文:m=L(cλ mod n2)×μ mod nm=L(c^\lambda \space mod \space n^2) \times \mu \space mod \space n

密文加法

  1. 密文:c1 and c2c_1 \space and \space c_2,计算:c=c1×c2 mod n2c=c_1 \times c_2 \space mod\space n^2cc 就是密文加法的结果

密文减法

  1. 密文:c1 and c2c_1 \space and \space c_2,计算:c=c1c2 mod n2c=\frac{c_1}{c_2} \space mod\space n^2cc 就是密文减法的结果

密文标量乘法

  1. 密文:c1c_1,明文标量:aa,计算:c=c1a mod n2c=c_1^a \space mod\space n^2cc 就是密文标量乘法的结果

正确性

加解密正确性

公式推导需要用到 Carmichael 函数和确定合数剩余的公式,下面简单说明一下:

  • Carmichael 函数
    1. n=pqn=pq,其中:p,qp,q为大素数
    2. 欧拉函数:ϕ(n)\phi(n),Carmichael函数:λ(n)\lambda(n)
    3. ϕ(n)=(p1)(q1)\phi(n)=(p-1)(q-1)λ(n)=lcm(p1,q1)\lambda(n)=lcm(p-1, q-1)时,其中:Zn2=ϕ(n2)=nϕ(n)\left|\mathbb{Z}_{n^2}^*\right|=\phi(n^2)=n\phi(n)。对于任意 wZn2w \in \mathbb{Z}_{n^2}^*,有如下性质:{wλ=1 mod nwnλ=1 mod n2\begin{cases} w^\lambda=1\space mod\space n \\ w^{n\lambda}=1\space mod\space n^2 \end{cases}
  • 判定合数剩余
    1. 判定合数剩余类问题是指n=pqn=pq,其中:p,qp,q为大素数,任意给定 yZn2y \in \mathbb{Z}_{n^2}^*,使得 z=yn mod n2z=y^n\space mod\space n^2,则说 zz是模n2n^2的第nn次剩余
    2. nn项剩余的集合是Zn2\mathbb{Z}_{n^2}^*的一个ϕ(n)\phi(n)阶乘法子集
    3. 每个第nn项剩余zz都正好拥有nnnn阶的根,其中只有一个是严格小于nn的(即 zn mod n\sqrt[n]{z}\space mod\space n
    4. nn项剩余都可以写成 (1+n)x=1+xn mod n2(1+n)^x=1+xn\space mod\space n^2的形式
  • 正确性验证
cλ mod n2=(gmrn)λ mod n2=gmλrnλ mod n2=gmλ mod n2=(1+n)mλ mod n2=1+nmλ mod n2\begin{align} c^\lambda\space mod\space n^2 & =(g^mr^n)^\lambda\space mod\space n^2 \\ & =g^{m\lambda}r^{n\lambda}\space mod\space n^2 \\ & =g^{m\lambda}\space mod\space n^2 \\ & =(1+n)^{m\lambda}\space mod\space n^2 \\ & =1+nm\lambda\space mod\space n^2 \\ \end{align} gλ mod n2=(1+n)λ mod n2=1+nλ mod n2\begin{align} g^\lambda\space mod\space n^2 & =(1+n)^\lambda\space mod\space n^2 \\ & =1+n\lambda\space mod\space n^2 \\ \end{align} L(cλ mod n2)=cλ mod n21n=1+nmλ mod n21n=mλ mod n2L(c^\lambda\space mod\space n^2)=\frac{c^\lambda\space mod\space n^2-1}{n}=\frac{1+nm\lambda\space mod\space n^2-1}{n}=m\lambda\space mod\space n^2 L(gλ mod n2)=gλ mod n21n=1+nλ mod n21n=λ mod n2L(g^\lambda\space mod\space n^2)=\frac{g^\lambda\space mod\space n^2-1}{n}=\frac{1+n\lambda\space mod\space n^2-1}{n}=\lambda\space mod\space n^2

解密:

m=L(cλ mod n2)×μ mod n=L(cλ mod n2)L(gλ mod n2) mod n=mλ mod n2λ mod n2 mod n=m mod n=m\begin{align} m & = L(c^\lambda \space mod \space n^2) \times \mu \space mod \space n \\ & = \frac{L(c^\lambda \space mod \space n^2)}{L(g^\lambda \space mod \space n^2)}\space mod \space n \\ & = \frac{m\lambda\space mod\space n^2}{\lambda\space mod\space n^2}\space mod \space n \\ & = m\space mod \space n \\ & = m \end{align}

密文加法正确性

Encrypt(m1)=c1Encrypt(m_1)=c_1Encrypt(m2)=c2Encrypt(m_2)=c_2

Decrypt(c)=Decrypt(c1×c2 mod n2)=Decrypt((gm1r1n×gm2r2n) mod n2)=Decrypt((gm1+m2(r1+r2)n) mod n2)=Decrypt((gm1+m2rn) mod n2)=m1+m2\begin{align} Decrypt(c) & = Decrypt(c_1 \times c_2 \space mod\space n^2) = Decrypt((g^{m_1}r_1^n\times g^{m_2}r_2^n)\space mod\space n^2) \\ & = Decrypt((g^{m_1+m_2}(r_1+r_2)^n)\space mod\space n^2)=Decrypt((g^{m_1+m_2}{r}^n)\space mod\space n^2)=m_1+m_2\\ \end{align}

密文减法正确性

Encrypt(m1)=c1Encrypt(m_1)=c_1Encrypt(m2)=c2Encrypt(m_2)=c_2

Decrypt(c)=Decrypt(c1c2 mod n2)=Decrypt(gm1r1ngm2r2n mod n2)=Decrypt((gm1r1n×(gm2r2n)1) mod n2)=Decrypt((gm1r1n×gm2r2n mod n2)=Decrypt((gm1m2(r1r21)n) mod n2)=Decrypt((gm1m2rn) mod n2)=m1m2\begin{align} Decrypt(c) & = Decrypt(\frac{c_1}{c_2} \space mod\space n^2) = Decrypt(\frac{g^{m_1}r_1^n}{ g^{m_2}r_2^n}\space mod\space n^2) \\ & = Decrypt((g^{m_1}r_1^n\times (g^{m_2}r_2^n)^{-1})\space mod\space n^2) = Decrypt((g^{m_1}r_1^n\times g^{-m_2}r_2^{-n}\space mod\space n^2) \\ & = Decrypt((g^{m_1-m_2}(r_1r_2^{-1})^n)\space mod\space n^2)=Decrypt((g^{m_1-m_2}{r}^n)\space mod\space n^2)=m_1-m_2\\ \end{align}

密文标量乘法正确性

Encrypt(m1)=c1Encrypt(m_1)=c_1

Decrypt(c)=Decrypt(c1a mod n2)=Decrypt((gm1rn)a mod n2)=Decrypt((gam1(ra)n) mod n2)=Decrypt((gam1r1n) mod n2)=am1\begin{align} Decrypt(c) & = Decrypt(c_1^a \space mod\space n^2) = Decrypt((g^{m_1}r^n)^a\space mod\space n^2) \\ & = Decrypt((g^{am_1}(r^a)^n)\space mod\space n^2)=Decrypt((g^{am_1}r_1^n)\space mod\space n^2)=am_1\\ \end{align}

算法实现

接口定义

  • 对象相关接口

    • 公/私钥对象:PAILLIER_KEY,该对象用来保存 paillier 公钥和私钥的基本信息,比如p,q,n,g,λ,μp,q,n,g,\lambda,\mu等信息,私钥保存所有字段,公钥只保存 n,gn,g,其他字段为空或者0。相关接口如下:

      // 创建 PAILLIER_KEY 对象
      PAILLIER_KEY *PAILLIER_KEY_new(void);

      // 释放 PAILLIER_KEY 对象
      void PAILLIER_KEY_free(PAILLIER_KEY *key);

      // 拷贝 PAILLIER_KEY 对象,将 src 拷贝到 dest 中
      PAILLIER_KEY *PAILLIER_KEY_copy(PAILLIER_KEY *dest, PAILLIER_KEY *src);

      // 复制 PAILLIER_KEY 对象
      PAILLIER_KEY *PAILLIER_KEY_dup(PAILLIER_KEY *key);

      // 将 PAILLIER_KEY 对象引用计数加1,释放 PAILLIER_KEY 对象时若引用计数不为0则不能释放其内存
      int PAILLIER_KEY_up_ref(PAILLIER_KEY *key);

      // 生成 PAILLIER_KEY 对象中的参数,bits 为随机大素数 p、q 的二进制位长度
      int PAILLIER_KEY_generate_key(PAILLIER_KEY *key, int bits);

      // 获取 key 的类型:公钥 or 私钥
      // PAILLIER_KEY_TYPE_PUBLIC 为私钥,PAILLIER_KEY_TYPE_PRIVATE 为私钥
      int PAILLIER_KEY_type(PAILLIER_KEY *key);
    • 上下文对象:PAILLIER_CTX,该对象用来保存公私钥对象以及一些其他内部用到的信息,是 paillier算法其他接口的第一个参数。相关接口如下:

      // 创建 PAILLIER_CTX 对象,key 为 paillier 公钥或者私钥,threshold 为支持最大的数字阈值,加密场景可设置为0,解密场景可使用默认值:PAILLIER_MAX_THRESHOLD
      PAILLIER_CTX *PAILLIER_CTX_new(PAILLIER_KEY *key, int64_t threshold);

      // 释放 PAILLIER_CTX 对象
      void PAILLIER_CTX_free(PAILLIER_CTX *ctx);

      // 拷贝 PAILLIER_CTX 对象,将 src 拷贝到 dest 中
      PAILLIER_CTX *PAILLIER_CTX_copy(PAILLIER_CTX *dest, PAILLIER_CTX *src);

      // 复制 PAILLIER_CTX 对象
      PAILLIER_CTX *PAILLIER_CTX_dup(PAILLIER_CTX *src);
    • 密文对象:PAILLIER_CIPHERTEXT,该对象是用来保存 paillier 加密后的结果信息,用到PAILLIER_CIPHERTEXT的地方,可调用如下接口:

      // 创建 PAILLIER_CIPHERTEXT 对象
      PAILLIER_CIPHERTEXT *PAILLIER_CIPHERTEXT_new(PAILLIER_CTX *ctx);

      // 释放 PAILLIER_CIPHERTEXT 对象
      void PAILLIER_CIPHERTEXT_free(PAILLIER_CIPHERTEXT *ciphertext);
  • 加密/解密接口

    // 加密,将明文 m 进行加密,结果保存到 PAILLIER_CIPHERTEXT 对象指针 out 中
    int PAILLIER_encrypt(PAILLIER_CTX *ctx, PAILLIER_CIPHERTEXT *out, int32_t m);

    // 解密,将密文 c 进行解密,结果保存到 int32_t 指针 out 中
    int PAILLIER_decrypt(PAILLIER_CTX *ctx, int32_t *out, PAILLIER_CIPHERTEXT *c);
  • 密文加/减/标量乘运算接口

    // 密文加,r = c1 + c2
    int PAILLIER_add(PAILLIER_CTX *ctx, PAILLIER_CIPHERTEXT *r,
    PAILLIER_CIPHERTEXT *c1, PAILLIER_CIPHERTEXT *c2);

    // 密文标量加,r = c1 * m
    int PAILLIER_add_plain(PAILLIER_CTX *ctx, PAILLIER_CIPHERTEXT *r,
    PAILLIER_CIPHERTEXT *c1, int32_t m);

    // 密文减,r = c1 - c2
    int PAILLIER_sub(PAILLIER_CTX *ctx, PAILLIER_CIPHERTEXT *r,
    PAILLIER_CIPHERTEXT *c1, PAILLIER_CIPHERTEXT *c2);

    // 密文标量乘,r = c * m
    int PAILLIER_mul(PAILLIER_CTX *ctx, PAILLIER_CIPHERTEXT *r,
    PAILLIER_CIPHERTEXT *c, int32_t m);
  • 编码/解码接口

同态加密涉及到多方参与,可能会需要网络传输,这就需要将密文对象PAILLIER_CIPHERTEXT编码后才能传递给对方,对方也需要解码得到PAILLIER_CIPHERTEXT对象后才能调用其他接口进行运算。 接口如下:

// 编码,将密文 ciphertext 编码后保存到 out 指针中,out 指针的内存需要提前分配好;
// 如果 out 为 NULL,则返回编码所需的内存大小;
// flag:标志位,预留,暂时没有用
size_t PAILLIER_CIPHERTEXT_encode(PAILLIER_CTX *ctx, unsigned char *out,
size_t size,
const PAILLIER_CIPHERTEXT *ciphertext,
int flag);

// 解码,将长度为 size 的内存数据 in 解码后保存到密文对象 r 中
int PAILLIER_CIPHERTEXT_decode(PAILLIER_CTX *ctx, PAILLIER_CIPHERTEXT *r,
unsigned char *in, size_t size);

以上所有接口详细说明请参考 paillier API 文档:https://www.yuque.com/tsdoc/api/slgr6f

核心实现

  • Paillier Key

    Paillier 不像 EC-ElGamal,EC-ElGamal 在 Tongsuo 里面直接复用 EC_KEY 即可,Paillier Key 在 Tongsuo 里面则需要实现一遍,主要功能有:公/私钥的生成、PEM 格式存储、公/私钥解析和文本展示,详情请查阅代码:crypto/paillier/paillier_key.c、crypto/paillier/paillier_asn1.c、crypto/paillier/paillier_prn.c

  • Paillier 加解密、密文运算

    Paillier 的加解密和密文运算算法非常简单,主要是大数的模幂运算,使用 Tongsuo 里面的 BN 相关接口就可以,需要注意的是,负数的加密/解密用到模逆运算,不能直接按公式计算(c=gmrn mod n2c=g^mr^n\space mod\space n^2),这是因为 Openssl 的接口BN_mod_exp没有关注指数(上面公式的 m)是不是负数,如果是负数的话需要做一次模逆运算:m=k,c=gmrn mod n2=gkrn mod n2=(gk)1rn mod n2m=-k,c=g^mr^n\space mod\space n^2=g^{-k}r^n\space mod\space n^2=(g^k)^{-1}r^n\space mod\space n^2,这里计算出 gkg^k之后做一次模逆运算(BN_mod_inverse)再与rnr^n相乘;解密的时候,需要检查是否检查了阈值(PAILLIER_MAX_THRESHOLD),超出则说明是负数,需要减去 n 才得到真正的结果。 密文减法也需要用到模逆运算,通过密文减法的公式(c=c1c2 mod n2=c1c21 mod n2c=\frac{c_1}{c_2} \space mod\space n^2=c_1c_2^{-1}\space mod\space n^2)得知,c2c_2需要进行模逆运算(BN_mod_inverse)再与c1c_1相乘。 详情请查阅代码:crypto/paillier/paillier_crypt.c

  • Paillier 命令行

    为了提高 Paillier 的易用性,Tongsuo 实现了如下 paillier 子命令:

    $ /opt/tongsuo-debug/bin/openssl paillier -help
    Usage: paillier [action options] [input/output options] [arg1] [arg2]

    General options:
    -help Display this summary

    Action options:
    -keygen Generate a paillier private key
    -pubgen Generate a paillier public key
    -key Display/Parse a paillier private key
    -pub Display/Parse a paillier public key
    -encrypt Encrypt a number with the paillier public key, usage: -encrypt 99, 99 is an example number
    -decrypt Decrypt a ciphertext using the paillier private key, usage: -decrypt c1, c1 is an example ciphertext
    -add Paillier homomorphic addition: add two ciphertexts, usage: -add c1 c2, c1 and c2 are tow example ciphertexts, result: E(c1) + E(c2)
    -add_plain Paillier homomorphic addition: add a ciphertext to a plaintext, usage: -add_plain c1 99, c1 is an example ciphertext, 99 is an example number, result: E(c1) + 99
    -sub Paillier homomorphic subtraction: sub two ciphertexts, usage: -sub c1 c2, c1 and c2 are tow example ciphertexts, result: E(c1) - E(c2)
    -mul Paillier homomorphic scalar multiplication: multiply a ciphertext by a known plaintext, usage: -mul c1 99, c1 is an example ciphertext, 99 is an example number, result: E(c1) * 99

    Input options:
    -in val Input file
    -key_in val Input is a paillier private key used to generate public key

    Output options:
    -out outfile Output the paillier key to specified file
    -noout Don't print paillier key out
    -text Print the paillier key in text
    -verbose Verbose output

    Parameters:
    arg1 Argument for encryption/decryption, or the first argument of a homomorphic operation
    arg2 The second argument of a homomorphic operation

    主要命令有:

    • keygen:生成 paillier 私钥
    • pubgen:用 paillier 私钥生成公钥
    • key:文本显示 paillier 私钥
    • pub:文本显示 paillier 公钥
    • encrypt:对数字进行加密,输出 paillier 加密的结果,需要通过参数-key_in参数指定 paillier 公钥文件路径,如果加密负数则需要将-_代替,因为-会被 openssl 解析成预定义参数了(下同)
    • decrypt:对 paillier 密文进行解密,输出解密结果,需要通过-key_in参数指定 paillier 私钥文件路径
    • add:对两个 paillier 密文进行同态加法操作,输出同态加法密文结果,需要通过参数-key_in参数指定 paillier 公钥文件路径
    • add_plain:将 paillier 密文和明文相加,输出同态加法密文结果,需要通过参数-key_in参数指定 paillier 公钥文件路径
    • sub:对两个 paillier 密文进行同态减法操作,输出同态减法密文结果,需要通过参数-key_in参数指定 paillier 公钥文件路径
    • mul:将 paillier 密文和明文相乘,输出同态标量乘法密文结果,需要通过参数-key_in参数指定 paillier 公钥文件路径

    通过以上命令即可在命令行进行 Paillier 算法实验,降低入门门槛,详情请查阅代码:apps/paillier.c

    另外还实现了 paillier 的 speed 命令,可以进行性能测试,详情请查阅代码:apps/speed.c

    用法&例子

    demo 程序

    paillier_test.c
    #include <stdio.h>
    #include <time.h>
    #include <openssl/paillier.h>
    #include <openssl/pem.h>

    #define CLOCKS_PER_MSEC (CLOCKS_PER_SEC/1000)

    int main(int argc, char *argv[])
    {
    int ret = -1;
    int32_t r;
    clock_t begin, end;
    PAILLIER_KEY *pail_key = NULL, *pail_pub = NULL;
    PAILLIER_CTX *ctx1 = NULL, *ctx2 = NULL;
    PAILLIER_CIPHERTEXT *c1 = NULL, *c2 = NULL, *c3 = NULL;
    FILE *pk_file = fopen("pail-pub.pem", "rb");
    FILE *sk_file = fopen("pail-key.pem", "rb");

    if ((pail_pub = PEM_read_PAILLIER_PublicKey(pk_file, NULL, NULL, NULL)) == NULL)
    goto err;
    if ((pail_key = PEM_read_PAILLIER_PrivateKey(sk_file, NULL, NULL, NULL)) == NULL)
    goto err;

    if ((ctx1 = PAILLIER_CTX_new(pail_pub, PAILLIER_MAX_THRESHOLD)) == NULL)
    goto err;
    if ((ctx2 = PAILLIER_CTX_new(pail_key, PAILLIER_MAX_THRESHOLD)) == NULL)
    goto err;

    if ((c1 = PAILLIER_CIPHERTEXT_new(ctx1)) == NULL)
    goto err;
    if ((c2 = PAILLIER_CIPHERTEXT_new(ctx1)) == NULL)
    goto err;

    begin = clock();
    if (!PAILLIER_encrypt(ctx1, c1, 20000021))
    goto err;
    end = clock();
    printf("PAILLIER_encrypt(20000021) cost: %lfms\n", (double)(end - begin)/CLOCKS_PER_MSEC);

    begin = clock();
    if (!PAILLIER_encrypt(ctx1, c2, 500))
    goto err;
    end = clock();
    printf("PAILLIER_encrypt(500) cost: %lfms\n", (double)(end - begin)/CLOCKS_PER_MSEC);

    if ((c3 = PAILLIER_CIPHERTEXT_new(ctx1)) == NULL)
    goto err;

    begin = clock();
    if (!PAILLIER_add(ctx1, c3, c1, c2))
    goto err;
    end = clock();
    printf("PAILLIER_add(C2000021,C500) cost: %lfms\n", (double)(end - begin)/CLOCKS_PER_MSEC);

    begin = clock();
    if (!(PAILLIER_decrypt(ctx2, &r, c3)))
    goto err;
    end = clock();
    printf("PAILLIER_decrypt(C20000021,C500) result: %d, cost: %lfms\n", r, (double)(end - begin)/CLOCKS_PER_MSEC);

    begin = clock();
    if (!PAILLIER_mul(ctx1, c3, c2, 800))
    goto err;
    end = clock();
    printf("PAILLIER_mul(C500,800) cost: %lfms\n", (double)(end - begin)/CLOCKS_PER_MSEC);

    begin = clock();
    if (!(PAILLIER_decrypt(ctx2, &r, c3)))
    goto err;
    end = clock();
    printf("PAILLIER_decrypt(C500,800) result: %d, cost: %lfms\n", r, (double)(end - begin)/CLOCKS_PER_MSEC);


    printf("PAILLIER_CIPHERTEXT_encode size: %zu\n", PAILLIER_CIPHERTEXT_encode(ctx2, NULL, 0, NULL, 1));

    ret = 0;
    err:
    PAILLIER_KEY_free(pail_key);
    PAILLIER_KEY_free(pail_pub);
    PAILLIER_CIPHERTEXT_free(c1);
    PAILLIER_CIPHERTEXT_free(c2);
    PAILLIER_CIPHERTEXT_free(c3);
    PAILLIER_CTX_free(ctx1);
    PAILLIER_CTX_free(ctx2);
    fclose(sk_file);
    fclose(pk_file);
    return ret;
    }

编译和运行

先确保 Tongsuo 开启 paillier,如果是手工编译 Tongsuo,可参考如下编译步骤:

# 下载代码
git clone git@github.com:Tongsuo-Project/Tongsuo.git


# 编译参数需要加上:enable-paillier
./config --debug no-shared no-threads enable-paillier --strict-warnings -fPIC --prefix=/opt/tongsuo

# 编译
make -j

# 安装到目录 /opt/tongsuo
sudo make install

编译 demo 程序

gcc -Wall -g -o paillier_test ./paillier_test.c -I/opt/tongsuo/include -L/opt/tongsuo/lib -lssl -lcrypto

生成 Paillier 公私钥

# 先生成私钥
/opt/tongsuo/bin/openssl paillier -keygen -out pail-key.pem
# 用私钥生成公钥
/opt/tongsuo/bin/openssl paillier -pubgen -key_in ./pail-key.pem -out pail-pub.pem

运行结果

$ ./paillier_test
PAILLIER_encrypt(20000021) cost: 3.202000ms
PAILLIER_encrypt(500) cost: 0.442000ms
PAILLIER_add(C2000021,C500) cost: 0.047000ms
PAILLIER_decrypt(C20000021,C500) result: 20000521, cost: 0.471000ms
PAILLIER_mul(C500,800) cost: 0.056000ms
PAILLIER_decrypt(C500,800) result: 400000, cost: 0.464000ms
PAILLIER_CIPHERTEXT_encode size: 0

铜锁的 C 代码风格

· 5 min read
Paul Yang
PMC Member of Tongsuo

铜锁采用类似于OpenSSL的代码风格(Coding Style)。因铜锁项目中存在多种编程语言,而C语言作为其中占比最大的一种,所以本文对铜锁的C语言代码风格进行定义。

一、缩进

缩进采用4个空格,禁止使用Tab。预处理指令,按照嵌套层次,使用1个空格作为缩进,例如:

#if
# define
# if
# define
# else
# define
# endif
#else
# define
#endif

#define

二、换行

禁止一行中写多个语句,例如下例是禁止的:

if (condition) do_this();
do_something_everytime();

原则上每行的长度为80个字符,即超过80个字符的行需要进行换行;除非换行后严重影响可读性,可不受80字符的行长度限制。对于用户可见的字符串,例如输出到命令行对用户起提示作用的字符串,则禁止换行,以防止无法使用grep等工具在代码中查找。

三、大括号配对和空格

对于非函数类语句,铜锁采用如下的大括号对齐风格:

if (x is true) {
we do y
} else if (conidtion) {
we do z
} else {
do something...
}

do {
...
} while (1);

switch (suffix) {
case 'G':
case 'g':
mem <<= 30;
break;
case 'M':
case 'm':
mem <<= 20;
break;
case 'K':
case 'k':
mem <<= 10;
/* fall through */
default:
break;
}

需要注意的是,对于switch语句,其中的case需要和switch对齐,而非进一步进行缩进。 对于函数,则大括号的起始位置有变化:

int function(int x)
{
body of function
}

此外,关于空格也有相关约定。在绝大部分的关键字后面,都需要加1个空格,例如:

if, switch, case, for, do, while, return

对于函数,以及行为类似函数的关键字,如sizeof, typeof, alignof和__attribute__等,其后则不需要添加空格,例如:

SOMETYPE *p = OPENSSL_malloc(sizeof(*p) * num_of_elements);

双元和三元运算符的两侧也需要添加1个空格,而一元运算符则无需添加空格:

=  +  -  <  >  *  /  %  |  &  ^  <=  >=  ==  !=  ?  : +=

以下无需添加空格:

& * + - ~ ! defined

foo++
--bar

foo.bar
foo->bar

定义指针的时候,型号需要靠近变量一侧,而不是类型一侧:

char *p = "something";
int *a = NULL;

四、命名规则

变量和函数的命名禁止使用匈牙利命名法或者任何的驼峰式命名法,例如下列变量和函数名称都是禁止的:

int iVar;
int myVar;
char *pChar;
int AFunctionThatHandlesSomething()

相反,使用小写字母加下划线为主的命名方式:

int temp;
int ctx;
char *p;
int do_signature();

铜锁继承自OpenSSL,因此部分导出的API也延续了OpenSSL的命名规律,也就是大写字母开头,后加下划线和小写字母表明函数用途的方式。此部分风格暂时继续沿用,后续根据铜锁重构的进展再进行调整。

五、注释

禁止使用//风格的注释。对于单行注释,使用:

/* .... */

对于多行注释,使用:

/*-
* This is the preferred style for multi-line
* comments in the OpenSSL source code.
* Please use it consistently.
*
* Description: A column of asterisks on the left side,
* with beginning and ending almost-blank lines.
*/

Tongsuo 支持半同态加密算法 EC-ElGamal

· 17 min read
Jin Jiu
Maintainer of Tongsuo

背景

随着大数据与人工智能的快速发展,个人隐私数据泄露和滥用时有发生,隐私安全问题也越来越被重视,国家于 2020 年施行密码法、2021 年施行个人信息保护法,对个人隐私数据和数据安全加密有更高的要求。因此,隐私计算也不断地被提及和关注,源于其有优秀的数据保护作用,使得『数据不出域、可用不可见』,限定了数据的使用场景,防止了数据的泄露,而引起了业界的热捧。 隐私计算是指在保护数据本身不对外泄露的前提下,实现数据共享和计算的技术集合,共享数据价值,而非源数据本身,实现数据可用不可见。 隐私计算对于个人用户来说,有助于保障个人信息安全; 对于企业来说,隐私计算是数据协作过程中履行数据保护义务的关键路径; 对于政府来说,隐私计算实现数据价值最大化的重要支撑。

隐私计算目前在金融、医疗、电信、政务等领域均在开展应用试验,比如:

  • 银行和金融机构在不泄露各方原始数据的前提下,进行分布式模型训练,可以有效降低信贷、欺诈等风险;
  • 医疗机构无需共享原始数据便可进行联合建模和数据分析,数据使用方在不侵犯用户隐私的情况下,可以使用建模运算结果数据,有效推动医疗行业数据高效利用;
  • ……

隐私计算的相关技术有多方安全计算(MPC)、可信执行环境(TEE)、联邦学习(FL)、同态加密(HE)、差分隐私(DP)、零知识证明(ZKP)、区块链(BC)等等。这些技术各有优缺点,隐私计算的产品或者平台也是由这些技术来搭建。

其中与密码学明显相关的是同态加密,目前同态加密算法的开源项目各有千秋,用户使用比较复杂。Tongsuo 作为基础密码库,应该提供一套简单易用和高效的同态加密算法实现和接口,让上层应用更方便简单地使用同态加密算法。

此外,随着隐私计算技术的兴起,蚂蚁集团推出了开箱即用、软硬件结合的隐私计算基础设施,一站式解决方案,即可信原生一体机。Tongsuo 作为蚂蚁可信原生一体机中的核心基础软件密码库,将同态加密等隐私计算所需的相关密码学能力整合其中,为可信原生一体机的用户带来更加便捷高效的使用体验。

同态加密

同态加密(Homomorphic Encryption, HE)是指满足密文同态运算性质的加密算法,按性质分为加法同态和乘法同态:

  • 加法同态
    1. 满足: E(x)E(y)=E(x+y)E(x) \oplus E(y)=E(x+y)
    2. 椭圆曲线加密算法满足加法同态:

E(x)=gxE(x)E(y)=gxgy=gx+y=E(x+y)E(x)=g^x \longrightarrow E(x) \oplus E(y)=g^x g^y = g^{x+y} = E(x+y)

  • 乘法同态
    1. 满足:E(x)E(y)=E(xy)E(x) \otimes E(y)=E(xy)
    2. RSA加密算法满足乘法同态:

E(x)=xeE(x)E(y)=xeye=(xy)e=E(xy)E(x)=x^e \longrightarrow E(x) \otimes E(y)=x^e y^e = (xy)^e = E(xy) 同态加密后得到密文数据,对密文数据进行同态加法或者乘法得到密文结果,将密文结果同态解密后可以得到原始数据直接加法或者乘法的计算结果,如下图: image.png 根据满足加法和乘法的运算次数又分为:全同态加密和半同态加密

  • 全同态加密( Fully Homomorphic Encryption, FHE )
    • 支持任意次的加法和乘法运算
    • 难实现、性能差(密钥过大,运行效率低,密文过大)
    • 主流算法:Gentry、BFV、BGV、CKKS
    • 需要实现的接口:(非本文重点,略)
  • 半同态加密(Partially Homomorphic Encryption, PHE)
    • 只支持加法或乘法中的一种运算,或者可同时支持有限次数的加法和乘法运算
    • 原理简单、易实现、性能好
    • 主流算法:RSA、ElGamal、Paillier
    • 需要实现的接口:
      • KeyGen():密钥生成算法,用于产生加密数据的公钥 PK(Public Key)和私钥 SK(Secret Key),以及一些公共参数 PP(Public Parameter)。
      • Encrypt():加密算法,使用 PK 对用户数据 Data 进行加密,得到密文 CT(Ciphertext)。
      • Decrypt():解密算法,使用 SK 对密文 CT 解密得到数据原文 PT(Plaintext)。
      • Add():密文同态加法,输入两个 CT 进行同态加运算。
      • Sub():密文同态减法,输入两个 CT 进行同态减法算。
      • ScalaMul() 或者 Mul():密文同态标量乘法,输入一个 CT 和一个标量 PT,计算 CT 的标量乘结果。

EC-ElGamal 原理

ElGamal 加密算法是基于 Diffie-Hellman 密钥交换的非对称加密算法,EC-ElGamal 是 ECC 的一种,是把ElGamal 移植到椭圆曲线上来的实现,主要计算有:椭圆曲线点加、点减、点乘、模逆和离散对数。

以下是 EC-ElGamal 的算法原理:

  • 公共参数:
    • G:椭圆曲线基点
    • SK:私钥,SK=d,d 是 0 到椭圆曲线的阶 q 之间的随机数
    • PK:公钥,PK=dG
  • 加密
    • 明文 m,随机数 r
    • 计算密文 C:C=Encrypt(m,r)=(rG,rPK+mG)C=Encrypt(m,r)=(rG,rPK+mG)
    • 明文 m 的取值范围为模 order(G) 的模空间,但实际使用时 m 需限制为较小的数(例如 32 比特长度),否则椭圆曲线离散对数问题(ECDLP)无法求解。
  • 解密
    • 计算 rPK:𝑟𝑃𝐾=𝑟𝑑𝐺=𝑑𝑟𝐺=𝑑𝐶[0]=𝑆𝐾𝐶[0]𝑟𝑃𝐾=𝑟∗𝑑∗𝐺=𝑑∗𝑟𝐺=𝑑∗𝐶[0]=𝑆𝐾∗𝐶[0]
    • 计算 mG:𝑚𝐺=𝑟𝑃𝐾+𝑚𝐺𝑟𝑃𝐾=𝐶[1]𝑟𝑃𝐾𝑚𝐺=𝑟𝑃𝐾+𝑚𝐺−𝑟𝑃𝐾=𝐶[1]−𝑟𝑃𝐾
    • 计算 mG 的 ECDLP,获得明文 m。
  • 密文加法、密文减法
    • 两个密文 C1,C2𝐶1=(𝑟1𝐺,𝑟1𝑃𝐾+𝑚1𝐺),𝐶2=(𝑟2𝐺,𝑟2𝑃𝐾+𝑚2𝐺)C_1 , C_2 \longrightarrow 𝐶_1=(𝑟_1 𝐺, 𝑟_1 𝑃𝐾+𝑚_1 𝐺), 𝐶_2=(𝑟_2 𝐺, 𝑟_2 𝑃𝐾+𝑚_2 𝐺)
    • 密文加:对 2 个密文的 2 个 ECC 点分别做点加,共 2 个点加,公式如下:
      • 𝐴𝑑𝑑(𝐶1,𝐶2)=(𝑟1𝐺+𝑟2𝐺,𝑟1𝑃𝐾+𝑚1𝐺+𝑟2𝑃𝐾+𝑚2𝐺)=((𝑟1+𝑟2)𝐺,(𝑟1+𝑟2)𝑃𝐾+(𝑚1+𝑚2)𝐺)=𝐸𝑛𝑐𝑟𝑦𝑝𝑡((𝑚1+𝑚2),(𝑟1+𝑟2))𝐴𝑑𝑑(𝐶_1, 𝐶_2 )=(𝑟_1 𝐺+𝑟_2 𝐺, 𝑟_1 𝑃𝐾+𝑚_1 𝐺+𝑟_2 𝑃𝐾+𝑚_2 𝐺)=((𝑟_1+𝑟_2 )𝐺,(𝑟_1+𝑟_2 )𝑃𝐾+(𝑚_1+𝑚_2 )𝐺)=𝐸𝑛𝑐𝑟𝑦𝑝𝑡((𝑚_1+𝑚_2 ),(𝑟_1+𝑟_2 ))
      • 如上公式与明文 m1+m2m_1+m_2 的同态加密结果一致:Encrypt((m1+m2),r)Encrypt((m_1+m_2), r),这里 r=r1+r2r=r_1+r_2
    • 密文减:对 2 个密文的 2 个 ECC 点分别做点减,共 2 个点减,公式如下:
      • 𝑆𝑢𝑏(𝐶1,𝐶2)=(𝑟1𝐺𝑟2𝐺,𝑟1𝑃𝐾+𝑚1𝐺𝑟2𝑃𝐾𝑚2𝐺)𝑆𝑢𝑏(𝐶_1,𝐶_2 )=(𝑟_1 𝐺−𝑟_2 𝐺,𝑟_1 𝑃𝐾+𝑚_1 𝐺−𝑟_2 𝑃𝐾−𝑚_2 𝐺) =((𝑟1𝑟2)𝐺,(𝑟1𝑟2)𝑃𝐾+(𝑚1𝑚2)𝐺)=𝐸𝑛𝑐𝑟𝑦𝑝𝑡((𝑚1𝑚2),(𝑟1𝑟2))=((𝑟_1−𝑟_2 )𝐺,(𝑟_1−𝑟_2 )𝑃𝐾+(𝑚_1−𝑚_2 )𝐺)=𝐸𝑛𝑐𝑟𝑦𝑝𝑡((𝑚_1−𝑚_2 ),(𝑟_1−𝑟_2 ))
      • 如上公式与明文 m1m2m_1-m_2 的同态加密结果一致:Encrypt((m1m2),r)Encrypt((m_1-m_2), r),这里 r=r1r2r=r_1-r_2
  • 密文标量乘法
    • 密文:𝐶1=(𝑟1𝐺,𝑟1𝑃𝐾+𝑚1𝐺)𝐶_1=(𝑟_1 𝐺, 𝑟_1 𝑃𝐾+𝑚_1 𝐺),明文:𝑚2𝑚_2
    • 对密文的 2 个 ECC 点分别用 𝑚_2 做点乘,共 2 个点乘,公式如下:
      • 𝑀𝑢𝑙(𝐶1,𝑚1)=(𝑚2𝑟1𝐺,𝑚2(𝑟1𝑃𝐾+𝑚1𝐺))𝑀𝑢𝑙(𝐶_1, 𝑚_1 )=(𝑚_2 𝑟_1 𝐺, 𝑚_2 (𝑟_1 𝑃𝐾+𝑚_1 𝐺)) =(𝑚2𝑟1𝐺,𝑚2𝑟1𝑃𝐾+𝑚2𝑚1𝐺)=𝐸𝑛𝑐𝑟𝑦𝑝𝑡(𝑚2𝑚1,𝑚2𝑟1)=(𝑚_2 𝑟_1 𝐺, 𝑚_2 𝑟_1 𝑃𝐾+𝑚_2 𝑚_1 𝐺)=𝐸𝑛𝑐𝑟𝑦𝑝𝑡(𝑚_2 𝑚_1, 𝑚_2 𝑟_1)
    • 如上公式与明文 m2m1m_2m_1的同态加密结果一致:Encrypt(m2m1,r)Encrypt(m_2m_1, r),这里 r=m2r1r=m_2r_1

算法实现

接口定义

  • 对象相关接口

    • 上下文对象:EC_ELGAMAL_CTX,该对象用来保存公私钥以及一些其他内部用到的信息,是 EC-ElGamal 算法其他接口的第一个参数。接口如下:

      //创建 EC_ELGAMAL_CTX 对象,key 为 ECC 公钥或者私钥的 EC_KEY 对象
      EC_ELGAMAL_CTX *EC_ELGAMAL_CTX_new(EC_KEY *key);

      //释放 EC_ELGAMAL_CTX 对象
      void EC_ELGAMAL_CTX_free(EC_ELGAMAL_CTX *ctx);
    • 解密表对象:EC_ELGAMAL_DECRYPT_TABLE,该对象用来保存解密表的内部信息。椭圆曲线离散对数问题(ECDLP)只有爆力破解的方法可求解,而爆力破解的速度比较慢,通常的做法是使用小步大步算法(Baby-Step,Giant-Step,BSGS)。总体思想是提前将所有可能的明文结果提前运算后,保存到 hash 表中,下次只需要进行少量的运算和 hash 表查找就可以得到结果,大大提高 ECDLP 的解密效率,但解密表的初始化可能比较慢,而且解密表的实现事关解密速度,后面考虑可以开放接口的实现给上层应用,所以这里先定义了一个解密表的对象和默认实现。接口如下:

      //创建 EC_ELGAMAL_DECRYPT_TABLE 对象
      //decrypt_negative 为 1 时表示该解密表可以解密负数,初始化解密表时将可能的负数运算后插入到 hash 中。
      EC_ELGAMAL_DECRYPT_TABLE *EC_ELGAMAL_DECRYPT_TABLE_new(EC_ELGAMAL_CTX *ctx,
      int32_t decrypt_negative);

      //释放 EC_ELGAMAL_DECRYPT_TABLE 对象
      void EC_ELGAMAL_DECRYPT_TABLE_free(EC_ELGAMAL_DECRYPT_TABLE *table);

      //设置 EC_ELGAMAL_DECRYPT_TABLE 对象到上下文对象中
      //解密时如果存在解密表则使用解密表进行求解,否则直接爆力破解,速度会很慢
      void EC_ELGAMAL_CTX_set_decrypt_table(EC_ELGAMAL_CTX *ctx,
      EC_ELGAMAL_DECRYPT_TABLE *table);
    • 密文对象:EC_ELGAMAL_CIPHERTEXT,由上面原理可知,加密之后得到的结果是两个点,该对象是用来保存加密后的密文信息(两个点)。接口如下:

      //创建 EC_ELGAMAL_CIPHERTEXT 对象
      EC_ELGAMAL_CIPHERTEXT *EC_ELGAMAL_CIPHERTEXT_new(EC_ELGAMAL_CTX *ctx);

      //释放 EC_ELGAMAL_CIPHERTEXT 对象
      void EC_ELGAMAL_CIPHERTEXT_free(EC_ELGAMAL_CIPHERTEXT *ciphertext);
  • 加密/解密接口

    //加密,将明文 plaintext 进行加密,结果保存到 EC_ELGAMAL_CIPHERTEXT 对象指针 r 中
    int EC_ELGAMAL_encrypt(EC_ELGAMAL_CTX *ctx, EC_ELGAMAL_CIPHERTEXT *r, int32_t plaintext);

    //解密,将密文 ciphertext 进行解密,结果保存到 int32_t 指针 r 中
    int EC_ELGAMAL_decrypt(EC_ELGAMAL_CTX *ctx, int32_t *r, EC_ELGAMAL_CIPHERTEXT *ciphertext);
  • 密文加/减/标量乘运算接口

    //密文加,r = c1 + c2
    int EC_ELGAMAL_add(EC_ELGAMAL_CTX *ctx, EC_ELGAMAL_CIPHERTEXT *r,
    EC_ELGAMAL_CIPHERTEXT *c1, EC_ELGAMAL_CIPHERTEXT *c2);

    //密文减,r = c1 - c2
    int EC_ELGAMAL_sub(EC_ELGAMAL_CTX *ctx, EC_ELGAMAL_CIPHERTEXT *r,
    EC_ELGAMAL_CIPHERTEXT *c1, EC_ELGAMAL_CIPHERTEXT *c2);

    //标量密文乘,r = m * c
    int EC_ELGAMAL_mul(EC_ELGAMAL_CTX *ctx, EC_ELGAMAL_CIPHERTEXT *r,
    EC_ELGAMAL_CIPHERTEXT *c, int32_t m);
  • 编码/解码接口

同态加密涉及到多方参与,可能会需要网络传输,这就将密文对象 EC_ELGAMAL_CIPHERTEXT 编码后才能传递给对方,对方也需要解码得到 EC_ELGAMAL_CIPHERTEXT 对象后才能调用其他接口进行运算。

接口如下:

//编码,将密文 ciphertext 编码后保存到 out 指针中,out 指针的内存需要提前分配好;
//如果 out 为 NULL,则返回编码所需的内存大小;
//compressed 为是否采用压缩方式编码,1 为压缩编码(编码结果长度较小),0 为正常编码(编码结果长度较大)
size_t EC_ELGAMAL_CIPHERTEXT_encode(EC_ELGAMAL_CTX *ctx, unsigned char *out,
size_t size, EC_ELGAMAL_CIPHERTEXT *ciphertext,
int compressed);

//解码,将长度为 size 的内存数据 in 解码后保存到密文对象 r 中
int EC_ELGAMAL_CIPHERTEXT_decode(EC_ELGAMAL_CTX *ctx, EC_ELGAMAL_CIPHERTEXT *r,
unsigned char *in, size_t size);

核心实现

Tongsuo 是 OpenSSL 的衍生版,内部支持了很多椭圆曲线算法的实现。比如,已支持国际(prime256v1、secp384r1 等)和国密(SM2)的大部分椭圆曲线,天生实现了椭圆曲线点运算、公私钥生成等基础算法,所以在 Tongsuo 实现 EC-ElGamal 算法的核心实现主要是 EC-ElGamal 原理的实现和 ECDLP 求解算法的实现,总共几百行代码,查看代码请移步 github:https://github.com/Tongsuo-Project/Tongsuo/blob/master/crypto/ec/ec_elgamal.c

用法&例子

demo 程序

#include <stdio.h>
#include <time.h>
#include <openssl/ec.h>
#include <openssl/pem.h>

#define CLOCKS_PER_MSEC (CLOCKS_PER_SEC/1000)

int main(int argc, char *argv[])
{
int ret = -1;
uint32_t r;
clock_t begin, end;
EC_KEY *sk_eckey = NULL, *pk_eckey = NULL;
EC_ELGAMAL_CTX *ctx1 = NULL, *ctx2 = NULL;
EC_ELGAMAL_CIPHERTEXT *c1 = NULL, *c2 = NULL, *c3 = NULL;
EC_ELGAMAL_DECRYPT_TABLE *table = NULL;
FILE *pk_file = fopen("ec-pk.pem", "rb");
FILE *sk_file = fopen("ec-sk.pem", "rb");

if ((pk_eckey = PEM_read_EC_PUBKEY(pk_file, NULL, NULL, NULL)) == NULL)
goto err;
if ((sk_eckey = PEM_read_ECPrivateKey(sk_file, NULL, NULL, NULL)) == NULL)
goto err;

if ((ctx1 = EC_ELGAMAL_CTX_new(pk_eckey)) == NULL)
goto err;
if ((ctx2 = EC_ELGAMAL_CTX_new(sk_eckey)) == NULL)
goto err;

begin = clock();
if ((table = EC_ELGAMAL_DECRYPT_TABLE_new(ctx2, 0)) == NULL)
goto err;

EC_ELGAMAL_CTX_set_decrypt_table(ctx2, table);
end = clock();
printf("EC_ELGAMAL_DECRYPT_TABLE_new(1) cost: %lfms\n", (double)(end - begin)/CLOCKS_PER_MSEC);

if ((c1 = EC_ELGAMAL_CIPHERTEXT_new(ctx1)) == NULL)
goto err;
if ((c2 = EC_ELGAMAL_CIPHERTEXT_new(ctx1)) == NULL)
goto err;

begin = clock();
if (!EC_ELGAMAL_encrypt(ctx1, c1, 20000021))
goto err;
end = clock();
printf("EC_ELGAMAL_encrypt(20000021) cost: %lfms\n", (double)(end - begin)/CLOCKS_PER_MSEC);

begin = clock();
if (!EC_ELGAMAL_encrypt(ctx1, c2, 500))
goto err;
end = clock();
printf("EC_ELGAMAL_encrypt(500) cost: %lfms\n", (double)(end - begin)/CLOCKS_PER_MSEC);

if ((c3 = EC_ELGAMAL_CIPHERTEXT_new(ctx1)) == NULL)
goto err;

begin = clock();
if (!EC_ELGAMAL_add(ctx1, c3, c1, c2))
goto err;
end = clock();
printf("EC_ELGAMAL_add(C2000021,C500) cost: %lfms\n", (double)(end - begin)/CLOCKS_PER_MSEC);

begin = clock();
if (!(EC_ELGAMAL_decrypt(ctx2, &r, c3)))
goto err;
end = clock();
printf("EC_ELGAMAL_decrypt(C20000021,C500) result: %d, cost: %lfms\n", r, (double)(end - begin)/CLOCKS_PER_MSEC);

begin = clock();
if (!EC_ELGAMAL_mul(ctx1, c3, c2, 800))
goto err;
end = clock();
printf("EC_ELGAMAL_mul(C500,800) cost: %lfms\n", (double)(end - begin)/CLOCKS_PER_MSEC);

begin = clock();
if (!(EC_ELGAMAL_decrypt(ctx2, &r, c3)))
goto err;
end = clock();
printf("EC_ELGAMAL_decrypt(C500,800) result: %d, cost: %lfms\n", r, (double)(end - begin)/CLOCKS_PER_MSEC);


printf("EC_ELGAMAL_CIPHERTEXT_encode size: %zu\n", EC_ELGAMAL_CIPHERTEXT_encode(ctx2, NULL, 0, NULL, 1));

ret = 0;
err:
EC_KEY_free(sk_eckey);
EC_KEY_free(pk_eckey);
EC_ELGAMAL_DECRYPT_TABLE_free(table);
EC_ELGAMAL_CIPHERTEXT_free(c1);
EC_ELGAMAL_CIPHERTEXT_free(c2);
EC_ELGAMAL_CIPHERTEXT_free(c3);
EC_ELGAMAL_CTX_free(ctx1);
EC_ELGAMAL_CTX_free(ctx2);
fclose(sk_file);
fclose(pk_file);
return ret;
}

编译和运行

  • 先确保 Tongsuo 开启 ec_elgamal,如果是手工编译 Tongsuo,可参考如下编译步骤:

    # 下载代码
    git clone git@github.com:Tongsuo-Project/Tongsuo.git


    # 编译参数需要加上:enable-ec_elgamal,我这里是在 macOS 系统上编译,所以是 darwin64-x86_64-cc,其他系统需要切换一下
    ./Configure darwin64-x86_64-cc --debug no-shared no-threads enable-ec_elgamal --strict-warnings -fPIC --prefix=/usr/local/tongsuo-debug

    # 编译
    make -j4

    # 安装到目录 /usr/local/tongsuo-debug
    sudo make install
  • 编译 demo 程序

    gcc -Wall -g -o ec_elgamal_test ./ec_elgamal_test.c -I/usr/local/tongsuo-debug/include -L/usr/local/tongsuo-debug/lib -lssl -lcrypto
  • 生成 ECC 公私钥

    # 先生成私钥,这里生成的是 SM2 曲线的私钥
    /usr/local/tongsuo-debug/bin/openssl ecparam -genkey -name SM2 -out ec-sk.pem
    # 用私钥生成公钥
    /usr/local/tongsuo-debug/bin/openssl ec -in ./ec-sk.pem -pubout -out ec-pk.pem
  • 运行结果

    $ ./ec_elgamal_test
    EC_ELGAMAL_DECRYPT_TABLE_new(0) cost: 2557.715000ms
    EC_ELGAMAL_encrypt(20000021) cost: 1.448000ms
    EC_ELGAMAL_encrypt(500) cost: 1.605000ms
    EC_ELGAMAL_add(C2000021,C500) cost: 0.014000ms
    EC_ELGAMAL_decrypt(C20000021,C500) result: 20000521, cost: 12.748000ms
    EC_ELGAMAL_mul(C500,800) cost: 1.562000ms
    EC_ELGAMAL_decrypt(C500,800) result: 400000, cost: 1.137000ms
    EC_ELGAMAL_CIPHERTEXT_encode size: 66
  • 注意事项

EC_ELGAMAL_DECRYPT_TABLE_new 函数第二个参数指定是否支持负数解密,如果支持负数解密会影响解密性能,因为查询解密表的次数变多了,以及点的运算变多了,同时构造支持负数的解密表需要的时间也比较长,如下是支持负数解密的运行结果:

$ ./ec_elgamal_test
EC_ELGAMAL_DECRYPT_TABLE_new(1) cost: 99023.542000ms
EC_ELGAMAL_encrypt(20000021) cost: 1.451000ms
EC_ELGAMAL_encrypt(500) cost: 1.426000ms
EC_ELGAMAL_add(C2000021,C500) cost: 0.021000ms
EC_ELGAMAL_decrypt(C20000021,C500) result: 20000521, cost: 461.471000ms
EC_ELGAMAL_sub(C500,C2000021) cost: 0.025000ms
EC_ELGAMAL_decrypt(C500,C20000021) result: -19999521, cost: 830.430000ms
EC_ELGAMAL_mul(C500,800) cost: 1.568000ms
EC_ELGAMAL_decrypt(C500,800) result: 400000, cost: 261.117000ms
EC_ELGAMAL_CIPHERTEXT_encode size: 66