在本文中,我們將考慮幾種有用且有效的算法,用於 在 由短 Weierstrass 方程給出的 域 GF(p)上的橢圓曲線E
у^2 = х^3 + Ах + В
- 生成曲線E上的點的算法
- 加分算法
- 倍增點算法
- 尋找整數倍點的算法
- 尋找整數倍點的算法(標量乘法)
- 在具有給定大小 d 的 支持 supp (D)的曲線E 上 構造除數 D的算法
- Miller 算法用於從除數 D計算 Weil 函數f n, P的值 ,滿足 supp(D) ∩ {P, O} = ∅
- 配對 威爾
有限域(或 Galois 域)上的模運算(整數)
- x mod n 表示“除以 x 後的餘數 n”。換言之,如果 x = an + b 且 a, b ∈ 整數,且 0 ≤ b ≤ n − 1,則 x mod n = b 。
- 反向 :如果 ax = 1 mod n ,則 a是x mod n 的倒數 。有兩種流行的解決方法 : • 方法一 :嘗試 a < n的每個值 ,只要 xa mod n = 1。 • 方法二 :歐幾里德方法,通常用於解決大整數的逆問題,因此推薦使用使用方法1解決小整數反問題。
橢圓曲線點運算
橢圓曲線 E上的點 P(x 0 ,y 0 ) 表示其 x 0 和 y 0坐標 為域元素, x 0 和 y 0坐標 滿足方程。
- 在橢圓曲線上加點 :令 P、Q 和 R 為橢圓曲線上的三個點。添加點 P + Q = R。
- 橢圓曲線上的雙點 :令 P、Q 為橢圓曲線上的兩點。倍增點 P + P = 2P = Q
- 點乘法 :令 P 為曲線 E上的一個點 ,定義在等式中
- 點乘 nP 定義為 nP = P + P + P + … + P ( n 次),其中 n 為整數; nP 也是同一條 E曲線上的一個點 。
- aP = O的最小自然數 a 稱為 P的階 。
- 橢圓曲線密碼系統中廣泛需要點乘法。
分頻器
曲線 E上的除數 (Divisor) D 是表示 E上點的多重集的 便捷方式 ,寫為形式和

- E上所有除數的集合 用Div F q (E) 表示 ,並形成一個群,其中除數的加法是自然的。
- 零因子:這是所有 n P = 0 的因子,零因子 是 0 ∈ Div F q (E) 。
- 如果域 F q 不具體,可以省略,簡單寫成 Div(E) 表示除數群。
函數 f 除以 E
函數 f 被 E的除數用於表示函數f 和 E 的交點(及其重數) 。
配對威爾
由e m表示的 Weyl 配對 以一對點 P, Q ∈ E[m] 作為輸入 ,並 產生單位根 _m e m ( P , Q) 作為輸出 。Weyl 對的雙線性由方程表示
e m (P 1 + P 2 , Q) = e m (P 1 , Q) * e m (P2, В),
e m (P, Q 1 + Q 2 ) = e m (P, Q 1 ) * e m (P, Q 2 )。
Weil 對 P 和 Q 是數

其中 S ∈ E 是滿足條件 S ∉ {O, P, −Q, P − Q} 的任意點 。(這確保右側的所有量都已定義且非零。)可以檢查 e m (P,Q)的值不取決於f P 、 f Q 和 S 的選擇 。
一種高效的Weil配對計算算法
令 E 為橢圓曲線,令 P = (x P ,y P ) 和 Q = (x Q , y Q ) 為E 上的非零點 。
令 λ為連接P 和 Q 的直線的斜率 ,或者如果P = Q 則E 在 P 處的 切線的斜率 。(如果直線是垂直的,我們設置 λ = ∞。)定義函數 g P, Q on E 如下:

然後
div(g P, Q ) = [P] + [Q] — [P + Q] — [ O
米勒算法
令 m ≥並將m 的二進制擴展寫 為
m = m 0 + m 1 * 2 + m 2 * 2 2 +···+ m n — 1 2 n — 1
因為 m i ∈ {0, 1} 且 m n — 1 ≠ 0 。以下算法返回一個函數 f P 其除數滿足條件
div( f P ) = m [ P ] — [ mP ] — ( m — 1 ) [ O ],
其中算法使用的函數 g T, T 和 g T, P在 (a) 中定義。

特別地,如果 P ∈ E[m] ,則 div( f P ) = m [ P ] − m [ O ]。
要求
Python 3.5
numpy
git clone https://github.com/demining/CryptoDeepTools.git
cd CryptoDeepTools/04AlgorithmsForSecp256k/
pip3 install numpy
├── Curves.py <- Набор данных эллиптических кривых
├── Divisor.py <- Создать делитель
├── EllipticCurve.py <- Классы эллиптической кривой и точки на эллиптической кривой
├── EuclideanAlg.py <- Расширенный алгоритм Евклида
├── Helper.py <- Вспомогательные функции (обратные биты, мощность по модулю)
├── Pairing.py <- Спаривания Вейля, а так же Алгоритм Миллера
├── Tests.py <- Модульные тесты для функций
├── Tonelli_ShanksAlg.py <- Алгоритм Тонелли – Шенкса
├── main.py <- main
電報: https: //t.me/cryptodeeptech
視頻素材: https: //youtu.be/gFbiBCNPsFk