大足区城乡建设投资集团网站大连网站制作公司

大足区城乡建设投资集团网站,大连网站制作公司,国金紫郡府淮北论坛,wordpress手机版加搜索框这张图在讲一件事#xff1a;椭圆曲线标量乘法 K⋅P#xff08;也就是“用整数 K 去乘一个点 P”#xff09;在实现里#xff0c;最终会被拆成#xff1a;上层的 点运算#xff1a;EC-Double#xff08;倍点#xff0c;2Q#xff09;和 EC-Add#xff08;加点#x…这张图在讲一件事椭圆曲线标量乘法K⋅P也就是“用整数 K 去乘一个点 P”在实现里最终会被拆成上层的点运算EC-Double倍点2Q和EC-Add加点QP更底层的有限域运算FF-Mult / FF-Add / FF-Square域乘/域加/域平方1) Double-and-Add 是怎么把 K⋅P 拆开的图顶端写了n Key size通常指K的bit长度比如 256 位h Hamming weightK的二进制里1 的个数在经典二进制 **Double-and-Add倍加法**里从最高位扫到最低位每处理 1 个bit必做 1 次 Double→ 次数大约是 n严格说是 n−1遇到该bit为 1才做 1 次 Add→ 次数大约是 h严格说常见实现是 h−1看初始化方式所以图里从 K⋅P 分两条边到EC-Double上标nEC-Add上标h这就是 Double-and-Add 的核心计数逻辑。一个常见伪代码MSB-firstQ O // 无穷远点 for i from n-1 downto 0: Q 2Q // EC-Double每轮必做 if k_i 1: Q Q P // EC-Add看该位是否为1 return Q2) 图里为什么强调“倍点/加点”下面又分解成 FF 运算因为在椭圆曲线实现中点的坐标在有限域里比如​ 或​点公式里的加减乘平方最后全都落到域运算FF-Add域加通常很便宜模 p 加减FF-Square域平方在很多实现里比乘法略便宜/可优化FF-Mult域乘最贵涉及大整数乘法/约简图底部还写了复杂度暗示FF-Mult标成意思是大整数乘法在高阶算法FFT/NTT下可到这个量级至少强调“乘法是主成本”。FF-Add、FF-Square标 O(1)表示相对便宜更像“常数级开销”对比乘法的主导地位。3) 图上那些 7、13、4、5、7、1 是什么意思这些数字是在说一次点运算大概要用多少次域运算在某种坐标表示/公式下不同曲线、不同坐标系数字会变但“乘法最贵”这一结论不变。从图里读数一次EC-Double约等于7 次FF-Mult4 次FF-Add5 次FF-Square一次EC-Add约等于13 次FF-Mult7 次FF-Add1 次FF-Square你会发现加点比倍点更贵尤其多了很多乘法。现实工程里之所以会出现这种“几十个域运算的组合”通常是因为实现用的是射影坐标/雅可比坐标来避免“求逆inversion”因为域求逆往往比很多次乘法还贵。图里也刻意没画 inversion正是这个思路。4) 把整张图合起来Double-and-Add 的总体成本怎么估如果把一次倍点成本记为​一次加点成本记为那么再用图里的分解把成本进一步写成域乘/加/平方的数量级域乘次数域加次数域平方次数因为域乘最贵所以标量乘法的速度基本由“需要做多少次域乘”决定。5) 工程上 Double-and-Add 的两个关键点A. 性能优化方向减少EC-Add次数减少 h例如用NAF、wNAF、窗口法、预计算 P,3P,5P...降低一次加点/倍点的域乘数量选更优的坐标系/公式Jacobian、Edwards 等B. 安全侧信道问题朴素 Double-and-Add 的if bit1 then Add会让耗时/功耗/分支行为随bit变化可能泄露密钥。常见对策Montgomery ladder每一位都做固定模式的 doubleadd常数时间实现避免条件分支、避免数据相关内存访问下面用一个非常小的“玩具曲线”把椭圆曲线里的 **Double-and-Add倍点-加点**完整算一遍每一步都带模运算与逆元你就能直观看到图里“上层 EC-Double/EC-Add → 下层有限域运算”的含义。1) 选一条玩具曲线 基点取素域也就是所有计算都对 17 取模选点基点P(5,1)验证它在曲线上左边右边左右同为 1所以。2) 目标算 K⋅P取一个小整数 K13​bit长度 n4汉明重量 h31 的个数是 3这正对应你图里“EC-Double 约 ∼n、EC-Add 约 ∼h”的意思。3) 点加 / 倍点公式仿射坐标素域设。(1) 加点 P1≠P2​(2) 倍点然后同样算。这里的“”就是模逆元找一个数 t使得。4) 用 Double-and-Add从高位到低位计算 13P用一种常见写法先把最高位的 1 吃掉令 QP然后处理剩余位这样加点次数是 h−1。​最高位是 1所以先设接下来处理剩余三位1、0、1每一位都先Double若该位为 1 再Add P。第 1 位14.1 先倍点P(5,1)分母因为所以算坐标因此2P(6,3)4.2 再加点因为该位1(6,3)(5,1)−2 mod 1715−1 mod 1716且因为所以 3P(10,6)第 2 位04.3 只倍点Q2Q2(3P)6P对 (10,6) 倍点分母 12因为所以6P(16,13)该位为 0不加点第 3 位14.4 先倍点Q2Q12P对 (16,13) 倍点分子 3⋅125分母所以12P(0,11)4.5 再加点因为该位1Q12PP13P(0,11)(5,1)−10 mod 177因为最终13P(16,4)5) 和图的对应关系为什么 Double-and-Add 的成本长这样本例 n4处理剩余 3 位做了3 次 EC-Doubleh3除去最高位那次初始化做了2 次 EC-Add而图里进一步强调每次 EC-Double / EC-Add 都要展开成很多次有限域乘/加/平方并且域乘最贵所以整体性能基本看“要做多少次域乘”。