一年十二月谁主春秋关注：基础系统工程密码学人工智能

随笔-165 评论-223 文章-30 trackbacks-0

NTRU格密码一处恒等式的证明

先摘取文献[1]的NTRU密码算法描述

矩阵T及T^*的定义如下

再给出证明过程

参考文献
[1] Post-Quantum Cryptography

posted @ 2026-01-27 18:00 春秋十二月阅读(34) | 评论 (0) | 编辑收藏

关于线性码的主要结论及应用

符号定义

主要结论

在密码学中的应用

上述McEliece公钥算法成立的关键之一是G^pub=SGP。由前面的定理1可得出G^pub与G等价，
但隐藏了码结构，增加了密码分析的难度

上述红色下划线处的结论，其根据是推论1

这里的线性码下界定义本质跟定理7一样，从校验矩阵H的所有列向量中，选取0个向量（即向量0）生成的线性组合数 +
选取1个线性无关向量生成的线性组合数 + 选取2个无关向量生成的线性组合数 + … +
选取d₀-1个无关向量生成的线性组合数，不超过r个无关向量生成的线性组合总数。下面解释了红色下划线处的结论

参考文献

[1] 高等代数丘维声

[2] Finite fields Rudolf Lidl Harald Niederreiter

[3] Post-Quantum Cryptography

posted @ 2026-01-25 20:30 春秋十二月阅读(48) | 评论 (0) | 编辑收藏

关于LLL算法的补充证明

先摘录文献[1]中的LLL算法描述流程，及LLL约化基的定义

LLL约化基的定义如下（文献[1]定义13.12）

再证明上图红色方框三行伪代码的正确性（其它部分文献[1]已讲得比较具体）

参考文献

[1] 算法数论裴定一祝跃飞

[2] 高等代数丘维声

posted @ 2025-09-28 17:43 春秋十二月阅读(377) | 评论 (0) | 编辑收藏

关于分圆域的一般结论

参考文献

[1]代数与数论李超周悦

[2]抽象代数II 徐明曜赵春来

posted @ 2025-07-28 12:01 春秋十二月阅读(455) | 评论 (0) | 编辑收藏

一个欧拉数整除问题的两种证法

参考文献

[1] 代数学基础与有限域林东岱

[2] 抽象代数赵春来徐明曜

posted @ 2025-06-20 18:41 春秋十二月阅读(564) | 评论 (0) | 编辑收藏

有限域上的特征与指数和之扩展

符号含义

关于特征的结论

关于指数和的结论

参考文献

[1] 代数学基础与有限域林东岱

[2] 代数与数论李超周悦

[3] 关于群的一些结论及应用本人

posted @ 2025-06-05 09:30 春秋十二月阅读(267) | 评论 (0) | 编辑收藏

二元二次型的相似变换、正定性与正交分解

本文主要阐述用两种方法判断给定两个二元二次型是否相似，相似情况下的具体变换。
相似变换如果确定了，也利于判断正定性，因为相似二次型的正定性相同。最后讲到了正交分解，
给出怎么求相似的整数对角矩阵

基本定义

下述定义来自文献[1] 12.1节，有所扩展

变换求解

先来看运用解方程的方法

再来看用矩阵的观点方法，求解变换。这种方法更适合求解到对角型的变换

正交分解

参考文献

[1] 华罗庚文集数论卷2

[2] 高等代数丘维声

posted @ 2025-04-25 19:05 春秋十二月阅读(391) | 评论 (0) | 编辑收藏

关于群的一些结论及应用

【命题1】所有群同态的原像个数相同，即为核的大小

下面看下这个结论在文献[1]中3.2节的应用

【命题2】所有元素阶小于等于2 的群为交换群，且其阶为2的整数幂

该结论在https://zhuanlan.zhihu.com/p/644888274中的推论2.2证明中用到

【命题3】群中任一元的相对于正规子群的指数次幂属于正规子群，2阶正规子群必

属于群的中心

【定理1】模奇合数的既约乘法群，其中雅可比符号为1的元素构成它的子群，其阶为

既约乘法群群阶的一半

【定理2】设G是群，H、K是有限子群，则HK的大小等于H的阶与K的阶乘积除以H与K交群的阶

参考文献

[1] 椭圆曲线及其在密码学中的应用—导引 Andreas Enge

[2] 抽象代数I 赵春来徐明曜
[3] 华罗庚文集数论卷2

[4] 组合数学冯荣权宋春伟

posted @ 2025-04-22 21:18 春秋十二月阅读(390) | 评论 (0) | 编辑收藏

不定方程的代数数论解法

符号含义与适用前提

二次域的基本结论

x²-dy²=±1

x² + d = y³

x² + y² = n

参考文献
[1] 代数与数论李超周悦

posted @ 2024-12-23 11:33 春秋十二月阅读(409) | 评论 (0) | 编辑收藏

关于椭圆曲线的验证计算

符号含义

E 表示满足椭圆曲线Weierstrass方程上的点群

K 代数闭域，用来限制Weierstrass方程的系数与E中的点

E(K) 定义在K上的点群E

E/K 定义在K上的椭圆曲线E

End(E) E上的自同态环

域扩张分析

End(E)模与Z代数

极点首项系数

除子映射及同构

同种映射同态性的解释

Hasse定理之引理证明的补充

挠曲线及其个数

有限域上的椭圆曲线

一种确定型群阶计算法

奇素域上的算法应用

GF域上的群阶计算

Schoof算法正确性根本

一种计算椭圆曲线群的阶的确定型多项式时间算法，确定型是因为算法内部没有随机选择/概率抛币操作，多项式时间是因为域k的乘法与求逆总次数是O((logq)^6)
（q为k的大小，乘法与求逆相对加减运算显著耗时）。具体原理及流程详见参考文献[1]中5.2节。这里给出笔者的一些思考

1. Hasse定理（Frobenius自同态方程式）在扭点群上的限制亦成立，这决定了t模l的一个同余方程成立，且在模l的最小非负剩余系下解是唯一的

2. 孙子定理保证了某取值范围内的一个t模L（L为各素因子l的乘积）的唯一解，即由t模L各个素因子l的同余方程构成的同余方程组的解是唯一的

3. L必须大于t取值上限的2倍。这是为了算法求得的解满足上述2（否则在更小的L内得到的解不唯一，因L与t上限或下限间的某数可以与t模L同余）

4. 素因子l的选择排除2与椭圆曲线特征p。这是因为算法构造所依赖的一个引理之前提条件：为奇素数保证l次除子多项式属于k[X]，即引理论断有意义；
不等于p保证检测一个多项式f是否零多项式的充要条件成立，即可以用l次除子多项式去整除f来判断。另l为素数保证了与其它除子多项式（及其幂次）互素
另外发现了算法的一处瑕疵，即第4步预计算除子多项式与Frobenius自同态的复合少了两个值，这导致第5步可能崩溃，当依赖的后续两个复合多项式没被计算时。
这个纠正可通过修改第4步扩大2个值，或第5步通过除子多项式的递推公式按需计算

扭点的阶计算正确性根本

在密码学中的应用

选取原则

1. 排除超奇异椭圆曲线。这是为避免MOV等约化攻击，约化攻击时间复杂度是亚指数

2. 有限域的选择要使E(F_q)的群阶足够大。这是为了缓解Shanks及Pollard ρ攻击

3. E(F_q)存在阶为大素数的子群。这是为了抵抗Pohlig-Hellman攻击

对于第1点，就排除了char(K)=2或3且j(E)=0对应的如下标准形式曲线

Y²+α₃Y=X³+α₄X+α₆（α₃≠0）与 Y²=X³+α₄X+α₆

一种典型方案
椭圆曲线及有限域的选择使得|E(F_q)|=cm，且char(F_q) ∤ q+1-cm。其中m是一个大素数（通常不低于256位二进制长度，提供中长期安全性），c小于m。
m阶子群的生成元可通过以下方法确定：随机选择E上的一个有理点P，如果Q=cP为零元（即无穷远点），则重复选择，直到其不等于零元。
一旦找到了生成元，那么子群就可以构造出来了。下面分析正确性

参考文献

[1] 椭圆曲线及其在密码学中的应用—导引 Andreas Enge

[2] 算法数论裴定一、祝跃飞

[3] The Arithmetic of Elliptic Curves Joseph H. Silverman

[4] 标识密码学程朝辉

[5] 代数学基础与有限域林东岱

[6] 抽象代数I 赵春来徐明曜

[7] 代数与数论李超周悦

posted @ 2024-11-10 21:45 春秋十二月阅读(390) | 评论 (0) | 编辑收藏

仅列出标题

常用链接

留言簿(32)

随笔分类(164)

随笔档案(165)

文章分类(30)

关注的开源项目

最新随笔

积分与排名

最新评论

阅读排行榜

评论排行榜