支持JavaScript的平台上的后量子加密方案和密钥交换协议的可移植实现

袁野，1肖俊婷，1福岛一秀，2清本慎作，2和高木
刚3,4
1九州大学数学研究院，日本2KDDI研究有限公司，日本3东京大学 数理情报学系，日本4日本科学技术振兴机构CREST，日本
通信应致袁野；y‐yuan@math.kyushu‐u.ac.jp 2018年4月6日收到；2018年6月27日修订；2018年7月18日接受；2018年9月13日发表 学术编辑：李玟圭
版权所有©2018袁野等。本文为开放获取文章，依据知识共享署名许可协议发布，允许在任何媒介中不受限制地使用、传 播和复制，前提是正确引用原始作品。

1. 引言

量子计算的快速发展，加之肖尔算法[1]，对广泛使用 的基于整数分解和离散对数问题的RSA及椭圆曲线密码 学（ECC）构成了重大威胁。因此，后量子密码学（ PQC）在研究人员中引起了广泛关注。在物联网时代， 大量设备将连接到互联网，它们需要高效的抗量子方法 来保障安全与隐私。物联网软件应在任何架构上都能正 常运行，因此软件的可移植性变得更加重要。此外，网 页浏览器作为网络应用的重要平台，也应如此
具有后量子加密功能。作为一种流行的跨平台/浏览器 语言，JavaScript是可移植性解决方案之一，因为其 性能在过去几年中已显著提升。
基于格的密码学被认为能够抵御量子计算机的攻击， 由于其高效性和适用性，已从学术界到工业界获得了广泛 关注和深入研究。近年来，提出了一些基于格的密码学的 加密方案和密钥交换协议的衍生方案，例如[3–7]。这些 密码系统的实现已在一些文献中被报道[8–12]。然而，截 至目前，关于在JavaScript平台上实现基于格的密码学的 研究还非常少[13,14]。因此，我们希望研究其性能

表1：提供约128位安全性的选定参数摘要。
| Lizard | | | | | | |
| — | — | — | — | — | — | — |
| m | n | l= | p | q | t | α−1 |
| 960 | 608 | 256 | 1024 | 2 | 182 | |

环蜥蜴
n=	q	p	α−1	––	––	––
1024	256	154	––	––	––

Kyber
k	n	q	η	db=	dc1	dc2
3	256	7681	4	11	3

Frodo
b	l	m	n	q	σ
4	8	8	752	32768	1.3229

新希望
k	n	q	––	––	––
16	1024	12289	––	––	––

在具有JavaScript实现的现代计算平台上，对几种近期基于格的密码 系统进行研究。我们希望为后量子密码学的实际实现做出贡献。
我们在四种网页浏览器、微控制器Tessel2、安卓手机Xperia XZ以及PC和Mac上的其他支持JavaScript的平台上，实现并测试了 五种近期基于格的加密方案和公钥交换协议。我们选择了一种基于带 错误学习（LWE）和带舍入学习（LWR）问题的加密方案“ Lizard”，及其环变体“环蜥蜴”[15],，一种基于模LWE的加密方
案“Kyber”[16],，以及两种抗量子密钥交换协议“Frodo”[17]
和“新希望”[18],，它们分别基于LWE问题和环LWE问题。上述所 有密码系统均使用JavaScript实现。我们的实现实源代码可在 https://github.com/FuKyuToTo/lattice‐based‐cryptography获 取。
为了提供公平的比较，我们从池允熙等人[15], 、约佩·博斯等人 [16, 17],和埃尔德姆·阿尔基姆等人[18],在表1中总结的估算结果中， 选择了具有128位后量子安全性的参数。然而，目前存在多种不同的 模型用于估算基于格的密码学[19]的安全参数。对这些参数的具体量 子安全等级的分析超出了本文的范围，更详细的安全估计算法可参见 [20–22]。我们的参数应在NIST后量子密码标准化项目（NIST PostquantumCryptographyStandardization. https://csrc.nist.gov/Projects/Post‐Quantum‐Cryptography） 确定最终的安全参数后重新调整。
我们选择这五个密码系统的主要原因是它们涵盖了 基于LWE的密码学的大多数变体，我们将在第2节中介 绍。此外，上述密码系统的参数和密钥大小不太大，适 合在网页浏览器和小型设备上使用JavaScript实现。
本文的贡献可以总结如下：
(i)我们首先使用JavaScript实现了上述五种基于格 的加密方案和密钥交换协议。我们观察了实现的运 行时间，发现基于环‐LWE的密码系统的性能远高 于其他方案。例如，在网页浏览器上，
Kyber和新希望的整个计算过程可以在毫秒内完成； 即使是物联网设备Tessel2也足够快，仅需两秒钟 即可完成所有这些操作。我们的实现将在未来的工 作中进一步改进，以支持NIST后量子密码标准化 项目。
(ii)我们重构了我们的实现以加速基于环LWE的加 密算法的多项式操作。通过实现改进的数论变换 （NTT）和逆数论变换（见[23, 24]）并减少创建临 时实例的内存开销，与我们之前的工作相比（见[13]）， 我们大幅提高了多项式操作的效率。
(iii)我们的实现在可移植性和可扩展性方面表现良好。
我们的JavaScript代码可以在任何JavaScript运行环境 上直接执行而无需修改。更重要的是，通过比较和分析 这些性能差异，我们可以进一步针对特定平台优化我们 的实现。
本文的其余部分组织如下。我们将在第2节中解释 符号表示，简要介绍数学背景，并介绍所实现的密码系 统。我们将在第3节介绍实验平台，并在第4节描述我 们的实现技术。然后我们将在第5节展示在网页浏览器 上的性能报告，在第6节展示在物联网设备Tessel2、 安卓手机及其他平台上的性能报告。最后，我们在第 7节对本文进行总结。附录部分包含我们源代码使用示 例。

2. 基于格的密码学

在本节中，我们介绍与LWE、环LWE和LWR问题相关 的数学背景，并总结基于这些问题的后量子加密方案。

2.1. 符号表示

设n,q为正整数；我们将q表示为整数集合{0,1,…
, q −1}，并将 R= Z[x]/(x n+ 1),Rq = Z q [x]/(x n+ 1)表示为多项 式环。多项式用粗斜体字母表示，例如 a，而向量则用
用粗体小写字母（如k）和矩阵以及粗体大写字母（如A）表示。 对于整数 m ∈ N，我们定义模运算b ≡a modm的范围为[0,m)
∩Z。

2.2. LWE、环LWE和LWR问题

雷格夫于2005年使用整 数矩阵提出了原始的LWE问题[3]。设 m、n、q为正
整数；搜索LWE问题要求通过输入一对矩阵（A，b=
As+ e） ∈ Zm×n q × Zmq来找到一个秘密向量s ∈ Zn q。判 定LWE问题是区分来自Zmq的一个均匀分布的随机向量 与一个带噪声的内积b= As+e。通常，A的元 素是从Zq中随机选取的，而所谓的误差向量e ∈ Zm则 从某个目标概率分布χ中采样得到。基于LWE问题的密 码学使用一种特殊结构格，称为q‐ary格：
L⊥q(A)={k ∈ Z n | Ak ≡0 modq};
Lq(A)={k ∈ Z n, s ∈ Z m | k ≡ ATs modq}; (1)
q‐元格中的所有元素均通过q的整数模运算获得。
环LWE问题（参见[5]）是雷格夫原始LWE问题的一 种变体。如果每个关于 Rq的多项式都存在到理想Zn q的双 射映射，则Rq是一个理想格。给定多项式 a、 b ∈ Rq，环 LWE问题的搜索版本旨在恢复秘密s ∈ Rq，其中 a是均匀 选取的，而 b= a ⋅ s+ e包含一个从目标概率分布 χ中采 样的“误差” e ∈ R。判定环LWE问题类似于判定L WE问题：给定a、 b ∈Rq，我们需要区分 b是否也是均匀
选取的，或者是否存在一个多项式s ∈ Rq使得 b= a ⋅ s+ e
成立。如果没有加入任何误差，LWE和环LWE问题将退 化为简单的线性代数计算，易于求解。在最坏情况下，这 类LWE和环LWE问题可归约到理想格上的NP难问题—— 近似最短向量问题（α‐SVP）。
给定一个矩阵A={a1,...,a n} ∈Z m×n q 和一个带 舍入的内积b= ⌊As⌋p ∈ Z m p ，LWR问题（参见[25]）
是找到向量s ∈ Zn q
技术或所谓的去随机化技术与LWE不同：内积的每个 值b 在Zp上乘以一个舍入值 ⌊q/p⌋，而不是添加一个随 机误差值；因此，LWR中的误差是确定性的。

2.3. 离散高斯采样

对于实数 σ> 0，在x ∈ R处的 高斯分布定义为ρσ=exp(−π‖x‖/s2)，其中高斯参数
为s= σ√2π。定义在Z上的高斯分布的离散版本为Dσ(x)
=ρσ(x)/ρσ(Z)。为了确定何时忽略远端采样值的可忽略 概率，设置一个截尾因子 t> 0以确定采样值范围。为 实现目标离散高斯分布，选择合适长度的截尾因子是必 要的；否则，任何采样算法都无法覆盖该范围。截尾界 限密切相关
到安全离散高斯参数[26, 27]所允许的最大统计距离。
请注意，从离散高斯分布中采样值与从正态分布[28] 中采样是不同的。我们实现了改进的Knuth‐Yao算法 [27, 29]和改进的离散Ziggurat算法[30]来执行此类 采样。这些采样方法将在第4.1节中讨论。

2.4. 二项分布

二项分布是n次伯努利试验中成功次数 的离散概率分布。本文遵循[16, 18]中的定义，将Bk表 示为正整数k的中心二项分布：
Input: a binary string(a0,a1,…,ak−1,b0,b1,…,
bk−1)←󳨀{0,1}2k Output: an integer ∑k−1 i=0(ai −bi)
为了便于计算，我们仅在Zq上对整数进行采样和 计算。

2.5. Lizard和环蜥蜴

Lizard加密方案[15]由正整数h、 m、n、l、t、p、q ∈Z以及误差率α ∈R进行参数化，其
中模数t、p、q满足t | p | q。对于实数0<ρ<1，我们从
分布ZOn(ρ)中采样值(V1, V2,…,Vn)←󳨀{−1,0,1}n，使得
每个值Vi（i=1,2,…,n）的选取满足Pr[Vi= 0]=1 −ρ
且Pr[Vi= 1]= Pr[Vi= −1]= ρ/2。对于整数 0 ≤ h ≤m，
我们从分布HWTm(h)中采样值(V1,V2,…,Vn) ←󳨀{−1,0,
1} m，使其在这些值中恰好有h个非零元素。 在密钥生成过程中，我们通过从分布ZOn(1/2)中独
立采样列向量si ∈Z n q（i= 1,2,...,l）来选择矩阵S ={s1,...,sl} ∈Z n×l q 。输入一个矩阵A ∈Z m×n q ，其元素 从Zq中均匀选取；然后我们可以计算矩阵B= AS+ E
∈ Zm×l q ，其中误差矩阵E ∈Z m×l q根据DZ,αq选择。私钥 为S，公钥为(A,B) ∈Z m×n q × ∈ Z m×l q 。在加密过程中， 通过从分布HWTm(128)中选择一个随机向量r ∈ Zm， 我们计算一对(c1, c2)=(A Tr,BTr) ∈Z n q× Zl q 。给定消息 m ∈Z l t ，密文是(c󸀠 1 ,c󸀠 2) ，其中c󸀠 ∈Z n p 且c
󸀠
2⌉ ∈Z l p 。最后，在解密时输出 向量m󸀠= ⌊(t/p) ∗(c 󸀠 2 −S Tc󸀠 1)⌉ ∈Z l t 。
环蜥蜴加密方案[15]是Lizard的一个变种，基于 环LWE和环LWR问题的困难性。与Lizard相比，它具 有更优的密钥大小，并提供更快的加密和解密速度。以 下过程定义了环蜥蜴方案。
密钥生成。采样e ←󳨀 DZ ,αq；从 HWTn (128)中选择一个 “小”的随机多项式 s，以及一个均匀随机的多项式
a ∈ Rq ；然后输出公钥(a, b= a ⋅ s+ e)∈Rq×Rq 和私钥 s ∈R。

加密。从HWTn(128)中选择一个随机多项式r ；给定明文 m ∈{0,1}n，
然后计算c1= ⌊ ⌉ ∈ Rp p q ∗ a⋅r ⌉ ∈Rp c2= ⌊p 2 ∗m+ p q ∗ b⋅r
c1 c2
(/)()和 (/)(/)()。密文是这对(,)。
Decryption. Output ⌊(2/p) ∗(c2 − c1 ⋅ s)⌉ ∈{0,1}n.

2.6. Kyber

Kyber[16]是一种基于模块‐LWE[31, 32]的近期 选择明文攻击（ChosenPlaintextAttack‐）安全的加密 方案，可用于构建选择密文攻击（ChosenCiphertext Attack‐）安全的密钥封装机制（KEM）。本文重点研究 前者，即实现Kyber的公钥加密方案。对于正整数db、dc1 、 dc2 、k、n、η和模数q ∈ Z，Kyber需要生成小维度的矩 阵，每个矩阵包含若干个系数在Rq中的多项式作为其元素。
Kyber的压缩和解压缩函数定义如下：
Compressq(x,d)= ⌊(2qd) ∗x⌉ mod2d;
Decompressq(x,d)= ⌊(2qd) ∗x⌉.
(2)
在密钥生成过程中，从{0,1}n中均匀随机选择一个 二进制字符串 α。矩阵A ∈(Rq) k×k可通过方法 SHAKE‐128(α)预先生成，两个向量s,e从(Bη) k中采样。 我们计算= Compressq(As+ e,db)。私钥为s，公钥为
(A,b)。在加密过程中，我们生成向量r,e1 ←󳨀(Bη) k和 e2 ←󳨀 Bη。然后通过方法 Decompressq(b,db)从b获得
向量b1。给定消息m ∈ Zn 2，密文为(c1,c2)，其中c 1= Compressq(A Tr+e1,dc 1 )，c2= Compressq(b T 1 r+
e2+ ⌊q/2⌉ ∗m,dc 2 )。在解密过程中，我们计算u = Decompressq(c1,dc 1 )和k= Decompressq(c2,dc 2 )，然

2.7. Frodo

Frodo[17],是基于LWE问题的密钥交换协 议，其参数为 b,d,l,m,n,q ∈Z和一个实数σ> 0。矩 阵A ∈ Z n×n q 通过伪随机生成函数Gen()从seedA生成。
本文中，我们关注图1中的主要计算过程：跳过生 成函数 Gen()并预先计算矩阵A。设b󸀠=(log2q) −b，
对于矩阵M ∈ Zx×y q ， rounding函数 ⌊M⌉2b 和 cross −
rounding函数M2b分别定义如下：
rounding: ⌊M⌉2b= ⌊2− b 󸀠 ∗M⌉ mod2b;
cross −rounding:⟨M⟩2b= ⌊21 − b 󸀠 ∗M⌋mod2. (3)
协调函数rec2b() 在[33]中定义。输出V是最接近w ∈
Zq 的元素，使得V 2 b= 0 或1。爱丽丝和Bob可通过 此协调机制获得相同的共享密钥K。

2.8. NewHope

与另一种基于环LWE的密钥交换协议BCNS相比，[7], NewHope[18]
在参数选择、误差采样和协调机制方面实现了一些改进。NewHope是一种著名的基 于环LWE的密钥交换协议，因其在GoogleCanary频道中进行的实验而备受关注； 实验结果表明，NewHope在Google的后量子TLS实验中表现良好，同时计算成本 仍然较低（ h t t p s:// security.googleblog.com/2016/07/experimenting‐with‐post‐quantum.html）。
我们希望了解其在网页浏览器或其他物联网设备上通过JavaScript运行时的性能。
设k、n和模 q为正整数；与Kyber中的多项式环
定义类似，密钥和误差均在Rq 上。一个seedA是交换过 程的一个组成部分，由二进制字符串生成，用于通过 SHAKE-128方法输出一个多项式a ∈ Rq 。NewHope还 需要从二项分布Bk 中采样随机值。对于协调机制，我们 采用[18]中的方法，并在未来的工作中可能使用非浮点 运算[34]。NewHope概述见图2。

3. 实验运行环境

3.1. 网页浏览器

在网页浏览器上实现后量子密码学原语 是必要且紧迫的

图3：基于格的密码系统Lizard、环蜥蜴、Kyber、Frodo和新希望在Firefox上的运行时间（毫秒）

因为网页浏览器是NIST后量子密码标准化项目的关键平台之一。本文选择 MozillaFirefox57.0.3239.108、Opera53.0.2907.68和MicrosoftEdge 42.17134.1.0上执行相同的程序。我们希望观察这些网页浏览器之间的性能差 异。我们将在第5节展示几种基于格的密码系统在网页浏览器上的运行时间。

3.2. Tessel2

与旧型号类似，Tessel2是一款支持 JavaScript的嵌入式系统，内置Wi‐Fi功能，专为物联网 开发者设计。Tessel2配备了580MHz联发科 MT7620n芯片级路由器、+ 48MHzAtmelSAMD21协 处理器，运行基于OpenWRT构建的Linux，具有 64MBDDR2内存和32MB闪存。Tessel2兼容 Node.js，可直接运行JavaScript程序以控制各种物联网 模块；开发者可通过一对多功能端口轻松控制模块。
Tessel2还支持用其他编程语言进行编程；然而，部分浏 览器端JavaScript库或对象不受支持。

3.3. Android WebView、个人电脑和Mac电脑

Android内置 了一种类似浏览器的活动，称为WebView。它可用于将网页或 HTML文件作为用户界面的一部分进行显示。开发者可以构建 WebView活动，以便在应用程序中显示在线内容或用户数据。
Android4.4已将WebView的渲染引擎替换为Chromium的 V8引擎，以提供改进的JavaScript性能。我们选择在Android 4.4（KitKat）中的WebView对我们的JavaScript实现进行基准 测试，并在安卓手机XperiaXZSOV34（Android版本8.0.0 （Oreo））上运行了我们的JavaScript实现。
一些操作系统还提供工具，用于在shell/脚本中执行纯文本 文件。MicrosoftWindows脚本宿主（WSH）被描述为一种管 理工具，可为批处理文件提供脚本执行环境。WSH的Active Scripting语言引擎可以解释和运行JScript或VBScript等脚本文 件。类似地，Mac用户可以通过使用osascript命令在macOS上 运行JavaScript文件，该命令支持AppleScript脚本或其他开放 式脚本架构（OSA）语言脚本。
此外，一些非浏览器软件（如Node.js或帕西菲斯塔）也 提供JavaScript运行环境。与谷歌浏览器和Android WebView一样，Node.js也是基于GoogleV8JavaScript引 擎构建的，并提供了丰富的JavaScript模块，有助于开发。
帕西菲斯塔是一个简单的基于Java的开源项目，可构建 Linux环境，并能使用JavaScript升级OpenSSL；它可以在 https://github.com/ukiuni/pacifista下载。
我们的实现在一台测试用个人电脑和一台MacBookPro上 进行测量。测试用个人电脑的配置如下：中央处理器：I ntel(R)Core(TM)i5‐8250U@1.6GHz；8GBDDR3
RAM；256GB固态硬盘；Windows10build17134家庭版x64。
MacBookPro（15英寸，2017款）配备四核Intel(R) Core(TM)i7@2.8GHz处理器、16GB2133MHzLPDDR3内存 和512GB固态硬盘，搭载macOSHighSierra10.13.5操作系统。
测试用的PC和MacBookPro上分别安装了Node.js8.11.2和 Pacifista0.0.30。我们在上述四种JavaScript运行时环境中测试 了我们的实现。在PC上运行了WSH和Node.js，在Mac上运行 了osascript和Pacifista（具体命令见附录）。

4. JavaScript实现的高效算法

4.1 离散高斯采样

设l ∈ Z为概率二进制展开的精度，
n ∈ Z；存在n个二进制概率p0, p1,…，p n−1 ∈Z l 2。一 个概率矩阵Pmat=[p0, p1,…，p n−1] ∈Z l×n 2由所有计 算出的概率组成，每一列存储一个概率。令k0, k1,…，
k l−1 ∈Z n 2为Pmat的所有行；因此，Pmat可存储为一维数
ln 2，用于算法1。
由于计算能力有限，对于某些编程语言或平台而言， 概率计算会成为一项耗时操作。通常，离散高斯采样需 要高精度的浮点运算或较大的存储需求[35]以确保安 全级别。受在FPGA上实现克努特‐姚算法思想的启发 [27],，我们对其进行了修改并将其在JavaScript中实 现。此外，允许进行时间‐内存权衡的离散Ziggurat算法[30]也已被改进，以实现在选定平台上的可移植性。
在这种情况下，克努特‐姚算法的表现优于改进的离散 Ziggurat算法。事实上，由于特性不同，这两种采样算法在不同平台上的性能表现各异。因此，我们选择克努 特‐姚算法来加速离散高斯采样。

算法1：克努特‐姚算法。
Input:l,n ∈Z,概率数组
k=(k0, k1,...,k l−1) ∈Z ln 2 输出：样本值s ∈Z ∩[−tσ,tσ]
1令d=0,x=0,sign=0；
2当true时执行循环 3 r←󳨀{0,1}均匀地随机选择； 4 d=2d+r；
5对于 i= n 从0开始递减1执行
6 d=d − ki;
7 if d= −1 then
8 if i= 0 then sign←󳨀{0,1}均匀地随机选择； 9 else
10 sign←󳨀{−1,1}均匀地随机地； 11返回 s= sign ∗row; 12 endif 13如果 sign=1，则返回 s= i;
14 else
15 d=0; 16 r←󳨀{0,1}均匀地随机地； 17 d=2d+r; 18 x=0;
19继续
20 结束如果 21结束如果
22结束循环 23 x+=1;
24 endwhile

4.2. 数论变换

数论变换（NTT）是一种快速傅里叶变 换（FFT）的高效推广方法，它在有限域Zq(q> 0)上 进行变换，而非复数域ℂ。对于高次多项式的乘法，其 渐近复杂度更低，为 O(nlogn)。
当 n为2的幂且 q为满足q ≡ 1 mod2n的素数时，
NTT接受一个多项式a ∈ Rq 作为输入，其系数按标准顺
序排列，并输出另一个多项式a 󸀠= NTT(a)。 a 󸀠可定义 为a󸀠 i= ∑ n − 1 j=0a jω ij modq(i= 0,1,...,n − 1)，其中 ω
是Zq中的一个n次本原单位根。类似地，我们将逆数论变换
记为NTT− 1，使得 a= NTT− 1 (a 󸀠 )，其中 ai=
n− 1
∑
n − 1 j=0a 󸀠 jω − ij modq(n − 1,1,...,n − 1)，从而NTT − 1 的输出满足NTT− 1 (NTT(a))= a。
我们在之前的工作[12, 13]中实现了迭代正向数论 变换[11, 36]算法。Kyber和新希望都需要执行多项式 乘法，一些文献如[23, 24]提供了高效的多项式乘法方 法以结合位反转

算法2：库利‐图基(CT)前向数论变换(NTT)。
Input：多项式 a ∈Rq= Zq[x]/(x n+1)，以及一个以位逆序排列的查找表ΨreV ∈Z n q
Output：多项式 a 󸀠=NTT(a) ∈R q 1t=n;
2从 m= 1 到 n −1按m=2m执行
3 t=t/2;
4从 i=0 到 m −1 执行
5 j1=2 ∗i ∗t; 6 j2=j1+t −1; 7 S=ΨreV [m+i]; 8 对于j=j1 到 j2 执行
9 U=aj ; 10 V=aj+t ∗S; 11 aj= U+V modq;
12 aj+t= U −V modq;
13 结束循环 14结束循环 15结束循环
16返回 a。

算法3：格恩特曼‐桑德(GS)逆数论变换(NTT−1)。
Input：多项式 a󸀠 ∈Rq= Z q[x]/(xn+1)，以及一个查找表Ψ−1 reV ∈ Zn q以位逆序排列 Output：多项式 a=NTT −1(a󸀠) ∈Rq
1 t= 1;
2对于 m=n 到2按m=m/2执行
3 h=m/2,j1= 0;
4对于 i= 0 到h −1 执行
5 j2=j1+t −1; 6 S=Ψ−1 reV[h+i]; 7 对于j=j1 到 j2 执行
8 U=aj; 9 V=aj+t; 10 aj= U+Vmodq;
11 aj+t=(U −V) ∗S modq;
12 结束循环 13 j1=j1+2t; 14 endfor 15 t=2t;
16 endfor 17对于 i= 0 到 n −1 执行
18 ai=ai ∗n−1 modq;
19结束循环
20返回 a。
因为网页浏览器是NIST后量子密码标准化项目的关键平台之一。本文选择 Mozilla Firefox 57.0.2作为基准平台，并采用开源项目Alea（可用网址： https:// github.com/nquinlan/better-random-numbers-for-javascript-mirror） 作为我们的安全伪随机数生成器（PRNG）。为了进行比较，我们在Google Chrome 63.0.3239.108、Opera 53.0.2907.68和Microsoft Edge 42.17134.1.0上执行相同的程序。我们希望观察这些网页浏览器之间的性能差 异。我们将在第5节展示几种基于格的密码系统在网页浏览器上的运行时间。

3.2. Tessel2

与旧型号类似，Tessel2 是一款支持 JavaScript 的嵌入式系统，内置 Wi-Fi 功能，专为物联网开发者设计。Tessel2 配备了 580 MHz联发科 MT7620n芯片级路由器、+ 48MHz Atmel SAMD21 协处理器，运行基于OpenWRT构建的Linux，具有 64MB DDR2内存 和 32MB闪存。Tessel2 兼容 Node.js，可直接运行 JavaScript 程序以控制各种物联网模块；开发者可通过一对多功能端口轻松控制模块。
Tessel2 还支持用其他编程语言进行编程；然而，部分浏览器端JavaScript库或对象不受支持。

3.3. Android WebView、个人电脑和Mac电脑

Android内置了一种类似浏览器的活动，称为WebView。它可用于将网页或 HTML文件作为用户界面的一部分进行显示。开发者可以构建 WebView活动，以便在应用程序中显示在线内容或用户数据。
Android 4.4已将WebView的渲染引擎替换为Chromium的 V8引擎，以提供改进的JavaScript性能。我们选择在Android 4.4（KitKat）中的WebView对我们的JavaScript实现进行基准测试，并在安卓手机Xperia XZ SOV34（Android版本8.0.0 （Oreo））上运行了我们的JavaScript实现。
一些操作系统还提供工具，用于在shell/脚本中执行纯文本文件。Microsoft Windows脚本宿主（WSH）被描述为一种管理工具，可为批处理文件提供脚本执行环境。WSH的Active Scripting语言引擎可以解释和运行JScript或VBScript等脚本文件。类似地，Mac用户可以通过使用osascript命令在macOS上运行JavaScript文件，该命令支持AppleScript脚本或其他开放式脚本架构（OSA）语言脚本。
此外，一些非浏览器软件（如Node.js或帕西菲斯塔）也提供JavaScript运行环境。与谷歌浏览器和Android WebView一样，Node.js也是基于Google V8 JavaScript引擎构建的，并提供了丰富的JavaScript模块，有助于开发。
帕西菲斯塔是一个简单的基于Java的开源项目，可构建 Linux环境，并能使用JavaScript升级OpenSSL；它可以在 https://github.com/ukiuni/pacifista下载。
我们的实现在一台测试用个人电脑和一台MacBook Pro上进行测量。测试用个人电脑的配置如下：中央处理器：Intel(R) Core(TM) i5-8250U @1.6GHz；8GB DDR3 RAM；256GB固态硬盘；Windows 10 build 17134家庭版x64。
MacBook Pro（15英寸，2017款）配备四核Intel(R) Core(TM) i7 @2.8GHz处理器、16GB 2133MHz LPDDR3内存 和512GB固态硬盘，搭载macOS High Sierra 10.13.5操作系统。
测试用的PC和MacBook Pro上分别安装了Node.js 8.11.2和 Pacifista 0.0.30。我们在上述四种JavaScript运行时环境中测试了我们的实现。在PC上运行了WSH和Node.js，在Mac上运行了osascript和Pacifista（具体命令见附录）。

4. JavaScript实现的高效算法

4.1 离散高斯采样

设l ∈ Z为概率二进制展开的精度，n ∈ Z；存在n个二进制概率p0, p1,…，p n−1 ∈Z l 2。一个概率矩阵Pmat=[p0, p1,…，p n−1] ∈Z l×n 2由所有计算出的概率组成，每一列存储一个概率。令k0, k1,…，k l−1 ∈Z n 2为Pmat的所有行；因此，Pmat可存储为一维数 ln 2，用于算法1。
由于计算能力有限，对于某些编程语言或平台而言，概率计算会成为一项耗时操作。通常，离散高斯采样需要高精度的浮点运算或较大的存储需求[35]以确保安全级别。受在FPGA上实现克努特-姚算法思想的启发 [27]，我们对其进行了修改并将其在JavaScript中实现。此外，允许进行时间-内存权衡的离散Ziggurat算法[30]也已被改进，以实现在选定平台上的可移植性。
在这种情况下，克努特-姚算法的表现优于改进的离散 Ziggurat算法。事实上，由于特性不同，这两种采样算法在不同平台上的性能表现各异。因此，我们选择克努特-姚算法来加速离散高斯采样。

算法1：克努特-姚算法。
Input: l,n ∈Z, 概率数组
k=(k0, k1,…,k l−1) ∈Z ln 2
输出：样本值 s ∈Z ∩[−tσ,tσ]
1 令d=0,x=0,sign=0；
2 当 true 时执行循环
3 r←{0,1} 均匀地随机选择；
4 d=2d+r；
5 对于 i= n 从 0 开始递减 1 执行
6 d=d − ki;
7 if d= −1 then
8 if i= 0 then sign←{0,1} 均匀地随机选择；
9 else
10 sign←{−1,1} 均匀地随机地；
11 返回 s= sign ∗row;
12 endif
13 如果 sign=1，则返回 s= i;
14 else
15 d=0;
16 r←{0,1} 均匀地随机地；
17 d=2d+r;
18 x=0;
19 继续
20 结束如果
21 结束如果
22 结束循环
23 x+=1;
24 endwhile

4.2. 数论变换

数论变换（NTT）是一种快速傅里叶变换（FFT）的高效推广方法，它在有限域 Zq(q> 0) 上进行变换，而非复数域ℂ。对于高次多项式的乘法，其渐近复杂度更低，为 O(nlog n)。
当 n为2的幂且 q为满足q ≡ 1 mod2n的素数时，NTT接受一个多项式a ∈ Rq 作为输入，其系数按标准顺序排列，并输出另一个多项式a 󸀠= NTT(a)。 a 󸀠可定义为a󸀠 i= ∑ n − 1 j=0a jω ij mod q(i= 0,1,…,n − 1)，其中 ω是Zq中的一个n次本原单位根。类似地，我们将逆数论变换记为NTT− 1，使得 a= NTT− 1 (a 󸀠 )，其中 ai= n− 1 ∑ n − 1 j=0a 󸀠 jω − ij mod q(n − 1,1,…,n − 1)，从而NTT − 1 的输出满足NTT− 1 (NTT(a))= a。
我们在之前的工作[12, 13]中实现了迭代正向数论变换[11, 36]算法。Kyber和新希望都需要执行多项式乘法，一些文献如[23, 24]提供了高效的多项式乘法方法以结合位反转
具有 NTT计算；因此，本文中我们遵循最先进的方法，并实现如算法2 和 算法3 所示的优化 NTT/NTT− 1。
设ψ ∈ Z q为一个本原 2n-次单位根，满足ω= ψ2。我们写出两个多项式 f=(f0 ,f1 ,…,fn − 1) 和 f=(f0 , ψf1 ,…,ψn − 1fn − 1) ∈ Rq 。用于计算的多项式乘法 c= a ⋅ b ∈ Rq ，首先我们预计算 2n 个 ψ 和ψ− 1 的幂，然后将 n个ψ 和ψ− 1 的幂以位逆序存储在查找表ΨreV 、Ψ− 1 re V ∈ Zn q 中。因此，输入多项式的位逆操作可以合并到预计算中。然后我们得到负缠绕卷积 c=

算法2：库利-图基(CT) 前向数论变换 (NTT)。
Input：多项式 a ∈Rq= Zq[x]/(x n+1)，以及一个以位逆序排列的查找表 ΨreV ∈Z n q
Output：多项式 a 󸀠=NTT(a) ∈R q
1 t=n;
2 从 m= 1 到 n −1按 m=2m执行
3 t=t/2;
4 从 i=0 到 m −1 执行
5 j1=2 ∗i ∗t;
6 j2=j1+t −1;
7 S=ΨreV [m+i];
8 对于 j=j1 到 j2 执行
9 U=aj ;
10 V=aj+t ∗S;
11 aj= U+V mod q;
12 aj+t= U −V mod q;
13 结束循环
14 结束循环
15 结束循环
16 返回 a。

算法3：格恩特曼-桑德 (GS) 逆数论变换 (NTT−1)。
Input：多项式 a󸀠 ∈Rq= Z q[x]/(xn+1)，以及一个查找表 Ψ−1 reV ∈ Zn q以位逆序排列
Output：多项式 a=NTT −1(a󸀠) ∈Rq
1 t= 1;
2 对于 m=n 到 2按 m=m/2 执行
3 h =m/2,j1= 0;
4 对于 i= 0 到 h −1 执行
5 j2=j1+t −1;
6 S=Ψ−1 reV[h+i];
7 对于 j=j1 到 j2 执行
8 U=aj;
9 V=aj+t;
10 aj= U+V mod q;
11 aj+t=(U −V) ∗S modq;
12 结束循环
13 j1=j1+2t;
14 endfor
15 t=2t;
16 endfor
17 对于 i= 0 到 n −1 执行
18 ai=ai ∗n−1 mod q;
19 结束循环
20 返回 a。

5. 网页浏览器上的性能

我们实现了三种加密方案：Lizard、环-Lizard [15], Kyber [16], ，以及两种密钥交换协议：Frodo [17] 和 NewHope[18]，均使用JavaScript实现。需要再次指出的是，本文主要关注计算过程和离散高斯采样。因此，我们省略了关于均匀选择的公钥分量或二进制种子的生成、编码/解码函数的一些步骤。本节将详细讨论我们的实现性能。我们实现的简单用法在附录中有所描述。
作为对比，我们实现了这五种基于格的密码系统，其对应的后量子安全级别约为128位（见表1）。图3显示了我们在Firefox浏览器上执行实现的性能结果。正如我们所预期的，包括Kyber和新希望在内的基于环 LWE的密码系统明显非常高效。尽管Kyber的模数较大，但其密钥大小小于Lizard。Kyber的密钥生成速度比Lizard快400多倍，但Lizard的解密速度最快。环蜥蜴的密钥生成和加密速度分别比Lizard快60多倍和4倍以上；然而，Kyber仍然远比环蜥蜴高效。与Frodo相比，新希望在爱丽丝端和Bob端的运行速度分别快8倍以上和13倍以上。

图4：Lizard、环蜥蜴、Kyber、Frodo 和 新希望 在 Firefox 上的计算时间（毫秒）分解。

对于Lizard，我们将矩阵存储在二维数组中，以减少由于JavaScript中行优先顺序的矩阵约定而导致的矩阵乘法运行时间。具体而言，我们计算向量与矩阵转置的乘积，而不是计算矩阵-向量乘积。此外，在密钥生成中的s和加密中的r的元素仅包含来自集合{0,±1}的值；因此，如果被乘数等于 ±1，我们可以用加法和减法代替整数乘法。对于环蜥蜴，由于其模数为2的幂，我们使用卡拉楚巴算法来计算多项式乘法。
对于Kyber，我们跳过了二进制种子和多项式的生成。在密钥生成和加密过程中，我们预先计算了矩阵A和NTT (⌊q/2⌉ ∗m)，并从二项分布B4 中采样误差向量。Kyber中矩阵和向量的每个元素都是一个次数等于n −1(q ≡ 1mod 2n)的关于Rq 的多项式；因此，可以对Kyber应用数论变换（NTT）以高效地计算多项式乘法。设 i,j,k为正整数；我们假设矩阵A =(aij) ∈(Rq) k×k处于NTT域中，并且每个元素aij的系数按位逆序排列。在密钥生成过程中，我们对误差向量执行了NTT，使得公钥b的分量= NTT− 1 (ANTT (s)+NTT(e))只需进行6次NTT调用和3次NTT− 1调用 （如果k= 3）。类似地，在加密过程中通过分别调用 NTT 10次和NTT− 1 4次来计算 NTT− 1 (NTT(A T )NTT(r) + NTT(e1))和NTT − 1 (NTT(b T )NTT(r)+NTT(e2)+NTT( ⌊q/2⌉ ∗m))，并在解密过程中通过调用NTT 4次和 NTT− 1 1次输出NTT− 1 (NTT(s) Tu)。
对于Frodo，我们跳过了从二进制字符串生成seedA的步骤，并在爱丽丝的两端预计算了矩阵A 以及Bob端。在支持JavaScript的平台上执行浮点运算没有问题，但考虑到我们后续在内存受限设备上的开发，我们在rounding/cross-rounding和reconciliation函数中将浮点运算替换为整数运算。为了采样误差矩阵，我们采用了如算法1所示的改进的Knuth-Yao算法。
对于新希望，我们还执行了NTT/NTT−1以加速多项式乘法，这在基于环LWE的密码学JavaScript实现中是一个瓶颈（例如见[13,14]）。在此情况下，我们按照[18]（第7.1节，协议3）实现了新希望，但跳过了SHAKE-128方法、哈希函数SHA3-256以及密钥编码/解码函数。我们在爱丽丝和Bob端预先计算了多项式 a，并直接发送了多项式 b、 u、 r。与[24],中的方法相比，我们在 Bob端仅计算了NTT−1 (b ∘ NTT(s1)) + e 2 ，从而省略了 对NTT(e2) 的计算。
图4展示了我们实现的计算时间分解。尽管每种实现技术和性能各不相同，多项式和矩阵乘法仍然是最耗时的计算部分。在Lizard和Frodo中，矩阵乘法占至少 70%。在Kyber和新希望中，超过50%的运行时间花费在 NTT/NTT− 1上。除了环蜥蜴外，误差元素生成（包括离散高斯采样和二项式采样）在计算中所占运行时间较少，在Frodo中约占20%，在Lizard、Kyber和新希望中约占10%；离散高斯采样在环蜥蜴的密钥生成中约占50%。
我们在其他台式个人电脑浏览器（包括GoogleChrome、 Opera和 Edge）上执行了相同的JavaScript程序。以Kyber和 新希望为例，图5显示了这些网页浏览器上的运行时间。
似乎我们的实现在Chrome和Opera上的性能非常相似，而Firefox的性能优于Edge。

图5：Kyber 和 新希望 在 Firefox、谷歌浏览器、Opera 和 Microsoft Edge 上的运行时间（毫秒）.

6. 在其他支持JavaScript的平台 上的性能

在本节中，我们展示了在物联网设备Tessel2、安卓手机、 Windows和macOS上的实现性能比较。我们的实现在设计上是可移植的，可以直接在这些实验平台上运行而无需修改。在这种情况下，我们预先计算了随机值生成和离散高斯采样，因为在Tessel2等微控制器上的JavaScript中实现密码学安全伪随机数生成器存在困难（参见[13]）。

6.1. Tessel2

图6显示了在Tessel2上执行的我们实现的性能（对于 Lizard，密钥的大小太大，无法在Tessel2上生成）。请注意运行时间以seconds为单位进行测量。我们已在旧版 Tessel上实现了基于环LWE的加密方案[5] （参见[13]）。
与我们之前的工作类似，在Tessel2上获得的性能结果比在网页浏览器上的结果慢几个数量级。然而， Tessel2已升级了硬件规格，具备更强的计算能力。例如，Kyber的加密和解密速度比在Firefox上运行慢 1000多倍。但Kyber/新希望的性能仍然出乎意料地高，计算过程可在1到2秒内完成。尽管Kyber/新希望的计算比[5],更复杂，但通过我们的改进的实现，已在硬件性能和内存开销方面取得了显著效果。

图6：运行基于格的密码系统 Lizard、环蜥蜴、Kyber、Frodo 和新希望在 Tessel2 上的运行时间（第二）.

6.2. 安卓手机

WebView 是 Android 的 View 类的扩展，用于显示网页和应用程序。它在 Android 框架上提供的性能与其他网页浏览器不同。我们在搭载高通骁龙820 MSM8996/2.2GHz 双核 + 1.6GHz 的安卓手机 Xperia XZ au SOV34 上运行了我们的实现。

表2：安卓手机上的性能结果。
| 平均运行时间（毫秒） | 密钥生成 | 加密 | 解密 |
| — | — | — | — |
| Lizard | 1575.91 | 38.62 | 9.63 |
| 环蜥蜴 | 13.24 | 15.05 | 5.61 |
| Kyber | 3.57 | 5.78 | 2.14 |

平均运行时间（毫秒）	Alice0	Bob	Alice1
Frodo	38.10	88.03	0.79
新希望	5.14	10.08	2.68

6.3. Windows和macOS上的其他JavaScript运行时环境

为了进行比较，我们研究了我们的JavaScript实现在 PC和Mac上的性能。由于我们的实现具有出色的可移植性，因此在其他JavaScript运行时环境中直接执行我们的代码并不困难。这些环境依赖于特定的平台或操作系统进行脚本编写。例如，JavaScript脚本文件（.js类型）可以通过WScript.exe以图形用户界面模式运行，也可以通过调用CScript.exe在Windows命令提示符下运行；运行帕西菲斯塔需要安装Java运行时环境（JRE）。截至目前，后量子密码学在这些平台上JavaScript中的性能很少被研究。据我们所知，这项工作是首次对此进行的研究。在此情况下，我们在 Windows 10家庭版上使用了WSH和Node.js，在macOS 高塞拉上使用了osascript和帕西菲斯塔。

从表3、4、5和6可以看出，在WSH上运行 JavaScript代码与其他平台相比存在巨大的性能差距。
WSH的运行速度最慢；例如，Lizard在WSH上的密钥生成速度比osascript慢约100倍，加密速度慢250倍以上，解密速度慢150倍以上。NewHope在WSH上的运行速度比Firefox慢约15倍（不考虑随机值生成的开销）。
Node.js 在基于环-LWE 的密码系统方面几乎提供了最佳性能。例如，Kyber 运行速度约为

表3：WSH上的性能结果
| 平均运行时间（毫秒） | 密钥生成 | 加密 | 解密 |
| — | — | — | — |
| Lizard | 27021.1 | 372.2 | 72.3 |
| 环蜥蜴 | 145.44 | 283.19 | 140.37 |
| Kyber | 9.89 | 15.76 | 6.15 |

平均运行时间（毫秒）	Alice0	Bob	Alice1
Frodo	827.03	1102.92	12.70
新希望	8.85	17.51	6.67

表4：Node.js上的性能结果
| 平均运行时间（毫秒） | 密钥生成 | 加密 | 解密 |
| — | — | — | — |
| Lizard | 271.08 | 6.54 | 1.47 |
| 环蜥蜴 | 1.86 | 2.48 | 1.22 |
| Kyber | 0.44 | 0.67 | 0.27 |

平均运行时间（毫秒）	Alice0	Bob	Alice1
Frodo	7.04	14.73	0.13
新希望	0.20	0.64	0.19

比 osascript 快 2 倍，而 Ring-Lizard 比 Pacifista 快 10 倍以上。Node.js 的性能几乎与使用谷歌V8 JavaScript引擎的谷歌浏览器相同。
osascript 也是 macOS 上的一个有效平台；例如，在 osascript 上运行 Frodo 比在 Firefox 上略快；环蜥蜴的加密速度分别比 Xperia XZ au SOV34 和 Tessel2 快约 3 倍和 5000 倍。
帕西菲斯塔的运行速度低于Node.js和osascript，但仍高于WSH，且可与Android WebView相媲美；因此，其性能对开发者而言是可接受的。对于所有三种加密方案而言，例外情况是密钥生成的运行时间比加密的运行时间更长。

表5：osascript上的性能结果。
| 平均运行时间（毫秒） | 密钥生成 | 加密 | 解密 |
| — | — | — | — |
| Lizard | 209.99 | 1.43 | 0.41 |
| 环蜥蜴 | 3.10 | 4.66 | 2.44 |
| Kyber | 0.80 | 1.20 | 0.49 |

平均运行时间（毫秒）	Alice0	Bob	Alice1
Frodo	6.88	10.46	0.09
新希望	0.75	1.32	0.43

表6：Pacifista上的性能结果
| 平均运行时间（毫秒） | 密钥生成 | 加密 | 解密 |
| — | — | — | — |
| Lizard | 1301.54 | 24.67 | 5.76 |
| 环蜥蜴 | 43.77 | 34.24 | 17.97 |
| Kyber | 7.39 | 4.49 | 1.78 |

平均运行时间（毫秒）	Alice0	Bob	Alice1
Frodo	35.80	43.96	0.75
新希望	2.57	9.27	3.08

7. 结论

我们首先在JavaScript中实现了五种新的基于格的加密方案 （Lizard、环-Lizard、Kyber）和密钥交换协议（Frodo、 NewHope），并在网页浏览器、Tessel2、安卓手机以及 PC和Mac上的其他平台测试了它们的性能。由于具有良好的可移植性，我们的代码可以在任何支持JavaScript的平台上运行。我们使用数论变换（NTT）来提高多项式乘法的速度，并采用改进的Knuth-Yao算法进行离散高斯采样。我们报告了实现方案在多个支持JavaScript的平台上的性能结果；相比之下，基于环-LWE的密码系统表现出优于其他方案的性能。
我们的概念验证实现在一定程度上证明了某些基于格的密码系统可以高效地用JavaScript实现。因此，我们的工作可以为基于格的密码学在NIST的标准化进程中。在未来的工作中，我们期望针对特定平台改进实现，并在更多平台上研究更多的基于格的公钥加密方案和密钥封装机制，以支持 NIST后量子密码标准化项目。

附录 我们实现的简单用法

我们以 Lizard 为例，说明如何使用我们的源代码。

Web Browsers

为了在网页浏览器上运行Lizard，我们创建一个包含必要内容的HTML文件，如伪代码 1 所示。
prng.js 是我们的主要数字生成器，其中包含一个快速的 PRNG 算法。如果在 Opera 上执行 Lizard，我们还可以使用 ECMAScript 标准函数 Math.random()，该函数是安全实现的（参见 https://lists.w3.org/Archives/Public/public-webcrypto/2013Jan/0063.html）。
lizard random values.js 包含用于测试的预生成随机数。Lizard 的主要函数是 lizard.js 中的 testlizard()（见伪代码2）。

伪代码 1

<!-- lizard.html -->
<!DOCTYPE HTML>
<html>
<head>
<title>Lizard</title>
<meta charset="UTF-8">
<script type="text/javascript" src="../Utils/prng.js"></script>
<script type="text/javascript" src="lizard_random_values.js"></script>
<script type="text/javascript" src="lizard.js"></script>
</head>
<body></body>
</html>

伪代码 2

// 参数可以更改
var m = 960, n = 608, l = 256, t = 2, p= 256, q = 1024; // h,r,...
function testlizard() { //主函数
//...
randomPlaintext();
keyGeneration(l,m,n,q);
encryption(l,n,p,q);
decryption(l,q,t);
//...
}
testlizard(); // 调用主函数

安卓手机

我们使用Eclipse Kepler Service Release 2和安卓开发工具包（ADT，版本：23.0.7.2120684）创建安卓应用程序包（APK）文件。我们将必要的代码从那些. js文件中复制并粘贴到一个HTML文件中，以供项目使用。该HTML文件被放置在 assets文件夹内作为本地文件。然后我们

伪代码 3

//...
import android.app.Activity ;
import android.os.Bundle ;
import android.webkit.WebView ;
public class MainActivity extends Activity {
private WebView webview;

@Override
protected void onCreate(Bundle savedInstanceState ){
super.onCreate(savedInstanceState);
webview = new WebView (this);
webview.getSettings()
.setJavaScriptEnabled(true);
webview.loadUrl
("file:///android_asset/lizard.html");
setContentView(webview);
}
//...
}

修改 MainActivity.java 中的 onCreate() 函数（参见伪代码3）。
我们可以从 bin文件夹 导出创建的 .apk 文件，并将其安装在 安卓手机 上。

其他平台

我们复制必要的代码并将其粘贴到一个 .js 文件中。该程序可以在命令行外壳中执行；例如，如下所示。

Tessel2
需要在.js文件的顶部导入Tessel硬件的接口：

var tessel= require('tessel');

在命令行中输入

C:\tesel2-code>t2 run new_lizard.js

在 Tessel2 的 RAM 中运行 Lizard。

WSH

C:\新文件夹\Lizard>cscript new_lizard.js
C:\新文件夹\Lizard>wscript new_lizard.js

Node.js

C:\新文件夹\Lizard>node new_lizard.js

osascript

$ osascript new_lizard.js

帕西菲斯塔

$ bin/pacifista scripts/new_lizard.js

为了测量运行时间，我们可以调用 Date.now() 函数或 new Date().getTime() 函数，但 WSH 仅支持后者。
console.log() 向控制台写入一条消息。如果代码在 WSH 上执行，我们应该调用 WScript.Echo() 来显示消息：

function print(message){
//WScript.Echo(message);
console.log(message);
}

结果将如下所示输出（二进制明文是随机生成的） （见伪代码4）。

伪代码 4

测试蜥蜴：
输入：
m= 960 n= 608 l= 256 t= 2 p= 256 q= 1024
//...
明文输出 =
0,0,1,0,1,0,0,1,1,1,0,0,1,0,0,1,0,1,1,1,1,//...
结果 =
0,0,1,0,1,0,0,1,1,1,0,0,1,0,0,1,0,1,1,1,1,//...
成功！