铜锁在手，合规无忧​

近日，蚂蚁集团密码团队基于开源铜锁项目和蚂蚁集团自研的密码卡，获得了国家密码管理局商用密码检测中心颁发的商用密码产品认证证书，符合 GM/T 0028《密码模块安全技术要求》安全二级。采用软硬件结合的方案，即混合软件密码模块，助力用户在国密改造、密评、等保等过程中，更加严谨地满足我国商用密码技术合规的要求。

关于商用密码产品认证​

我国于 2020 年实施了《中华人民共和国密码法》（以下简称密码法），标志着密码技术的应用进入了依法管理的时代。《密码法》规定，我国的密码实行分类管理，即核心密码、普通密码和商用密码。核心密码和普通密码用于保护国家秘密信息，商用密码则用于保护不属于国家秘密的信息。当前，商用密码已经广泛应用于政务、金融、通信、交通、医疗、能源等各领域，为社会经济发展提供了有力的安全保障。

《密码法》提出推进商用密码检测认证体系建设，制定商用密码检测认证技术规范、规则，鼓励商用密码从业单位自愿接受商用密码检测认证，提升市场竞争力。商用密码检测、认证机构应当依法取得相关资质，并依照法律、行政法规的规定和商用密码检测认证技术规范、规则开展商用密码检测认证。要求对关键信息基础设施的密码应用安全性开展分类分级评估。《网络安全法》也明确规定关键信息基础设施运营者每年要自行或者委托第三方机构对信息系统安全性进行测评。密码应用安全性是测评的一项重要内容，应遵循密码法律法规要求。

商用密码检测机构针对生产厂家提交的商用密码产品，按照不同产品类别的相关要求，进行技术合规方面的多重检测。检测通过后，由检测机构为商用密码产品颁发《商用密码产品认证证书》，其中注明是基于何种产品标准和技术要求进行的检测，例如对于密码模块类型的商用密码产品，则需要符合 GM/T 0028《密码模块安全技术要求》 的各项规范。

《商用密码产品认证证书》是一种资质，表明了获得证书的商用密码产品在经过相关检测机构严格的测试后，在技术正确性、兼容性等方面是符合规范要求的，因此可以为使用该商用密码产品的用户提供更加严谨和正式的监管合规支撑，例如在密评、等保等认证体系中，均对密码相关产品或服务提出了相关资质的要求。

由于业内对于商用密码通常简称为 “国密”，因此《商用密码产品认证证书》也俗称为 “国密资质”。

铜锁 + 蚂蚁卡，软硬件结合​

关于铜锁

铜锁（Tongsuo）是一个提供现代密码学算法和安全通信协议的开源基础密码库，为存储、网络、密钥管理、隐私计算等诸多业务场景提供底层的密码学基础能力，实现数据在传输、使用、存储等过程中的私密性、完整性和可认证性，为数据生命周期中的隐私和安全提供保护能力。
铜锁开源项目已经由蚂蚁集团完成了向开放原子开源基金会的捐赠，成为基金会的“孵化期”项目，也是基金会唯一的密码学方向开源项目。在基金会孵化过程中，铜锁开源社区先后启动了 “铜锁嵌入式版” 和 “RustyVault密钥管理系统” 两个新项目的开发。蚂蚁集团在铜锁完成捐赠后持续对项目进行投入，成立了铜锁项目管理委员会，引入多家领军企业参与铜锁开源项目的管理，推动铜锁进入到了独立发展的新阶段。

采用软硬件结合的方式申请二级密码模块，利用蚂蚁卡的密码管理能力和高性能优势，结合铜锁密码库提供的算法API、国密安全传输协议（TLCP）和硬件引擎框架，为应用程序提供数据安全能力。

支持常用的国密算法，包括 SM2、SM3 和 SM4。具体的安全功能包括 SM2 加密和解密、SM2 签名和验签、SM3 杂凑、SM4 对称加解密、软件随机数发生器、国密传输 TLCP 通信功能（包括客户端和服务端）。

开源计划​

二级密码模块中涉及的软件部分（非密码卡相关代码），会全部回馈给开源社区，将于近期内合并到铜锁开源项目中。 未来，铜锁开源项目也会适配更多的密码硬件，同时也欢迎跟更多的密码设备厂商合作，基于铜锁开源项目和密码硬件，共同打造安全、合规的解决方案，满足企业国密改造、密评、等保等场景下的技术合规要求。

🎉 开源之夏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 语言、云原生体系支持等前沿领域。我们诚挚邀请所有对这些领域感兴趣的开发者前往开源之夏官网获取更多信息。

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

第一章 总则​

第一条 社区名称​

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

第二条 使命和愿景​

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

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

第三条 业务范围​

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或使用教程）

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

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

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

选择版本：铜锁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），单进程测试

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

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

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

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

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

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

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

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

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

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

Android：BabaSSL移动端软件密码模块​

证书编号：GM003312220220743

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

PNG格式

iOS：BabaSSL IOS端软件密码模块​

证书编号：GM003312220230052

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

PNG格式：

Linux：应用安全软件密码模块（Linux版）​

证书编号：GM003312220230044

PDF格式： 应用安全软件密码模块（Linux版）.pdf

PNG格式：

背景​

在《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,q$，满足 $gcd(pq, (p-1)(q-1))=1$，且满足 p 和 q 的长度相等；
2. 计算 $n=pq$以及$\lambda=lcm(p-1, q-1)$，$lcm$ 表示最小公倍数；
3. 随机选择整数 $g\gets \mathbb{Z}_{n^2}^*$，一般$g$的计算公式如下：
   1. 随机选择整数 $k \in \mathbb{Z}_{n}^*$
   2. 计算：$g=1+kn$，为了简化和提高性能，$k$一般选1，$g=1+n$
4. 定义 L 函数：$L(x)=\frac{x-1}{n}$，计算：$\mu=(L(g^\lambda \space mod \space n^2))^{-1} \space mod \space n$
5. 公钥：$(n, \space g)$，私钥：$(\lambda, \space \mu)$

加密​

1. 明文 m，满足 $-n < m < n$
2. 选择随机数 r，满足 $0 \leq r<n$ 且 $r\in \mathbb{Z}_n^*$
3. 计算密文：$c=g^mr^n\space mod\space n^2$

解密​

1. 密文 c，满足 $c\in \mathbb{Z}_{n^2}^*$
2. 计算明文：$m=L(c^\lambda \space mod \space n^2) \times \mu \space mod \space n$

密文加法​

1. 密文：$c_1 \space and \space c_2$，计算：$c=c_1 \times c_2 \space mod\space n^2$，$c$ 就是密文加法的结果

密文减法​

1. 密文：$c_1 \space and \space c_2$，计算：$c=\frac{c_1}{c_2} \space mod\space n^2$，$c$ 就是密文减法的结果

密文标量乘法​

1. 密文：$c_1$，明文标量：$a$，计算：$c=c_1^a \space mod\space n^2$，$c$ 就是密文标量乘法的结果

正确性​

加解密正确性​

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

• Carmichael 函数
  1. 设 $n=pq$，其中：$p,q$为大素数
  2. 欧拉函数：$\phi(n)$，Carmichael函数：$\lambda(n)$
  3. 当 $\phi(n)=(p-1)(q-1)$和 $\lambda(n)=lcm(p-1, q-1)$时，其中：$\left|\mathbb{Z}_{n^2}^*\right|=\phi(n^2)=n\phi(n)$。对于任意 $w \in \mathbb{Z}_{n^2}^*$，有如下性质：$\begin{cases} w^\lambda=1\space mod\space n \\ w^{n\lambda}=1\space mod\space n^2 \end{cases}$
• 判定合数剩余
  1. 判定合数剩余类问题是指$n=pq$，其中：$p,q$为大素数，任意给定 $y \in \mathbb{Z}_{n^2}^*$，使得 $z=y^n\space mod\space n^2$，则说 $z$是模$n^2$的第$n$次剩余
  2. 第$n$项剩余的集合是$\mathbb{Z}_{n^2}^*$的一个$\phi(n)$阶乘法子集
  3. 每个第$n$项剩余$z$都正好拥有$n$个$n$阶的根，其中只有一个是严格小于$n$的（即 $\sqrt[n]{z}\space mod\space n$ ）
  4. 第$n$项剩余都可以写成 $(1+n)^x=1+xn\space mod\space n^2$的形式
• 正确性验证

解密：

密文加法正确性​

$Encrypt(m_1)=c_1$，$Encrypt(m_2)=c_2$

密文减法正确性​

$Encrypt(m_1)=c_1$，$Encrypt(m_2)=c_2$

密文标量乘法正确性​

$Encrypt(m_1)=c_1$

算法实现​

接口定义​

• 对象相关接口

  • 公/私钥对象：PAILLIER_KEY，该对象用来保存 paillier 公钥和私钥的基本信息，比如$p,q,n,g,\lambda,\mu$等信息，私钥保存所有字段，公钥只保存 $n,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=g^mr^n\space mod\space n^2$），这是因为 Openssl 的接口BN_mod_exp没有关注指数（上面公式的 m）是不是负数，如果是负数的话需要做一次模逆运算：$m=-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$，这里计算出 $g^k$之后做一次模逆运算（BN_mod_inverse）再与$r^n$相乘；解密的时候，需要检查是否检查了阈值（PAILLIER_MAX_THRESHOLD），超出则说明是负数，需要减去 n 才得到真正的结果。 密文减法也需要用到模逆运算，通过密文减法的公式（$c=\frac{c_1}{c_2} \space mod\space n^2=c_1c_2^{-1}\space mod\space n^2$）得知，$c_2$需要进行模逆运算（BN_mod_inverse）再与$c_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

铜锁采用类似于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.
 */

背景​

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

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

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

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

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

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

同态加密​

同态加密（Homomorphic Encryption, HE）是指满足密文同态运算性质的加密算法，按性质分为加法同态和乘法同态：

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

$E(x)=g^x \longrightarrow E(x) \oplus E(y)=g^x g^y = g^{x+y} = E(x+y)$

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

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

• 全同态加密（ 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)$
  • 明文 m 的取值范围为模 order(G) 的模空间，但实际使用时 m 需限制为较小的数（例如 32 比特长度），否则椭圆曲线离散对数问题（ECDLP）无法求解。
• 解密
  • 计算 rPK：$𝑟𝑃𝐾=𝑟∗𝑑∗𝐺=𝑑∗𝑟𝐺=𝑑∗𝐶[0]=𝑆𝐾∗𝐶[0]$
  • 计算 mG：$𝑚𝐺=𝑟𝑃𝐾+𝑚𝐺−𝑟𝑃𝐾=𝐶[1]−𝑟𝑃𝐾$
  • 计算 mG 的 ECDLP，获得明文 m。
• 密文加法、密文减法
  • 两个密文 $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 ))$
    • 如上公式与明文 $m_1+m_2$ 的同态加密结果一致：$Encrypt((m_1+m_2), r)$，这里 $r=r_1+r_2$
  • 密文减：对 2 个密文的 2 个 ECC 点分别做点减，共 2 个点减，公式如下：
    • $𝑆𝑢𝑏(𝐶_1,𝐶_2 )=(𝑟_1 𝐺−𝑟_2 𝐺,𝑟_1 𝑃𝐾+𝑚_1 𝐺−𝑟_2 𝑃𝐾−𝑚_2 𝐺)$ $=((𝑟_1−𝑟_2 )𝐺,(𝑟_1−𝑟_2 )𝑃𝐾+(𝑚_1−𝑚_2 )𝐺)=𝐸𝑛𝑐𝑟𝑦𝑝𝑡((𝑚_1−𝑚_2 ),(𝑟_1−𝑟_2 ))$
    • 如上公式与明文 $m_1-m_2$ 的同态加密结果一致：$Encrypt((m_1-m_2), r)$，这里 $r=r_1-r_2$
• 密文标量乘法
  • 密文：$𝐶_1=(𝑟_1 𝐺, 𝑟_1 𝑃𝐾+𝑚_1 𝐺)$，明文：$𝑚_2$
  • 对密文的 2 个 ECC 点分别用 𝑚_2 做点乘，共 2 个点乘，公式如下：
    • $𝑀𝑢𝑙(𝐶_1, 𝑚_1 )=(𝑚_2 𝑟_1 𝐺, 𝑚_2 (𝑟_1 𝑃𝐾+𝑚_1 𝐺))$ $=(𝑚_2 𝑟_1 𝐺, 𝑚_2 𝑟_1 𝑃𝐾+𝑚_2 𝑚_1 𝐺)=𝐸𝑛𝑐𝑟𝑦𝑝𝑡(𝑚_2 𝑚_1, 𝑚_2 𝑟_1)$
  • 如上公式与明文 $m_2m_1$的同态加密结果一致：$Encrypt(m_2m_1, r)$，这里 $r=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;
}