同源（isogeny）
椭圆曲线同源（isogeny）是椭圆曲线曲线理论中的核心概念
它描述两条椭圆曲线之间的特殊映射关系
我们在这里研究它的定义、核心性质，然后讨论它和weil对之间的关系，并在最后附上一道CTF真题
一、定义
设E1和E2是定义在同一域k上的两条椭圆曲线（标准形式为y2=x3+ax+b,其中a,b∈k）设E_1和E_2是定义在同一域k上的两条椭圆曲线（标准形式为y^2 = x^3 + ax+b,其中a,b\in k ）设E1和E2是定义在同一域k上的两条椭圆曲线（标准形式为y2=x3+ax+b,其中a,b∈k）
同源（isogeny） 是一个从 E1E_1E1 到$ E_2$ 的映射
ϕ:E1→E2\phi:E_1\to E_2ϕ:E1→E2，满足：
代数性：ϕ\phiϕ由域 k 上的有理函数（分式多项式）定义；
群同态：保持椭圆曲线的加法群结构，即对任意点 P,Q∈E1，有ϕ(P+Q)=ϕ(P)+ϕ(Q)P,Q\in E1，有 \phi(P+Q)=\phi(P)+\phi(Q)P,Q∈E1，有ϕ(P+Q)=ϕ(P)+ϕ(Q)；
非平凡性：不将所有点映射 ...
DES（Data Encryption Standard，数据加密标准）是一种经典的对称分组密码算法
它的核心是Feistel 网络结构，加密过程包括初始置换、16 轮迭代、子密钥生成、逆初始置换等关键步骤。
DES 处理的明文和密文均为64 位分组，使用的密钥为64 位（但实际参与加密的有效密钥长度为 56 位，剩余 8 位为奇偶校验位）。加密流程可概括为 5 个核心步骤：
明文经过初始置换（IP）；
生成 16 个子密钥（K₁~K₁₆）；
对初始置换后的结果进行16 轮 Feistel 迭代；
迭代结束后交换左右两部分；
经过逆初始置换（IP⁻¹） 得到密文。
但是有个巨大的问题，56位的密钥对于现代计算机来说简直脆的像个巧克力蛋筒，早在1998年就被暴力破解。目前DES已经被AES(高级加密标准)取代。
（缅怀）
一、初始置换(IP,Initial Permutation)
IP置换的目的是将64位明文的位进行重排列
我们来看标准IP置换表：
输出位范围(n)
对应输入明文的位（IP [n]）
1~16
58, 50, 42, 34, 26, 18, 10, 2 ...
Elgamal加密算法是一种基于离散对数问题的、基于迪菲-赫尔曼密钥交换协议的非对称加密算法
它的加解密过程还挺简单易懂的
首先我们准备好食材：
一个大素数p、一个Zp∗Z_p^*Zp∗的生成元g、随机选择整数k(0≤k≤p−2)k(0 \le k \le p-2)k(0≤k≤p−2)
然后计算y≡gkmod py \equiv g^k \mod{p}y≡gkmodp
这样子我们记私钥为{k}\{k\}{k} 公钥为{p,g,y}\{ p,g,y\}{p,g,y}
起锅烧水！！
Alice选取一个整数r，并计算如下两个方程
y1≡grmod py_1 \equiv g^r \mod py1≡grmodp (1)
y2≡myrmod py_2 \equiv my^r \mod py2≡myrmodp (2)
这样做就把m隐藏在y2y_2y2中
Alice再把y1 y2y_1\ y_2y1 y2发送给Bob
不难发现加密过程使用的是公钥{p,g,y}\{ p,g,y\}{p,g,y}
Bob还原m的过程也非常简单
将y≡gkmod py \ ...
a
MOV 攻击是 1993 年 Menezes，Okamoto 和 Vanstone 三人提出的一种攻击椭圆曲线离散对数问题（ECDLP）的方法，主要思路是利用双线性配对将椭圆曲线上的离散对数问题转化为有限域上的离散对数问题进行求解。
MOV攻击有效的条件
MOV攻击是否有效，取决于椭圆曲线的嵌入度
嵌入度是一个我们还没见过的概念
在密码学中，嵌入通常指的是将一个数学结构(如群、环或域)嵌入到另一个数学结构中。
假设在有限域Fq\Bbb{F}_qFq上有一条椭圆曲线EEE, E(Fq)E(\Bbb{F}_q)E(Fq)表示椭圆曲线EEE上的Fq\Bbb{F}_qFq - 有理点构成的群
嵌入度是满足椭圆曲线群阶的最大素因子NNN整除qm−1q^{m}-1qm−1的最小正整数m
（这里N其实代表阶最大的子群）
即对于给定的椭圆曲线E和子群阶N，嵌入度k是使得椭圆曲线群中阶为N的子群能够嵌入到有限域Fqk\Bbb{F}_{q^k}Fqk中的最小指数。
嵌入度越小MOV攻击越容易生效，但这里的小并没有严格的标准。因为MOV攻击核心是要向嵌入有限域Fqk\Bbb{F}_{q^k}Fq ...
E
ECDSA（Elliptic Curve Digital Signature Algorithm，椭圆曲线数字签名算法）是一种基于椭圆曲线密码学（ECC）的数字签名标准，用于验证数据的完整性（未被篡改）、真实性（确实来自发送方）和不可否认性（发送方无法否认发送行为）
它相比于RSA等签名算法，密钥长度更短，计算效率更高，因而得到广泛应用。
核心流程
ECDSA的核心流程分为密钥生成、签名生成和签名验证三个阶段
需要预先约定一条椭圆曲线E（记其模数为n）、基点 G
1.密钥生成
私钥：随机选择整数 d，满足$ 1<d<n−1$（n 为基点 G 的阶）。
公钥：通过点乘计算$ Q=d⋅G$（Q 是椭圆曲线上的点，与私钥 d 一一对应）。
！！私钥应当严格保密！！
2. 签名生成（发送方操作）
最终生成的签名的形式为(r,s)(r,s)(r,s)
计算消息msg的哈希值: h=Hash(msg)h = Hash(msg)h=Hash(msg),取h的整数形式(如果过长，通常阶段至与n同长)
生成随机整数k，满足1<k<n−11<k<n-11< ...
在面对各个各个算法的时候，我们常常常常见到“多项式时间”这个标准。
多项式都知道哇，∑i=0naixin\sum_{i=0}^{n}{a_ix_i^n}∑i=0naixin
我们就把多项式记为P(n)
那么倘若求解一个问题，需要进行的操作次数满足：T(n)=O(P(n))T(n) = O(P(n))T(n)=O(P(n)),这里多项式P(n)就刻画了求解这一问题的时间复杂度,
我们也称这一问题可以在多项式时间内完成
哎那我们怎么就逮着多项式不放呢？为什么不说指数时间、阶乘时间呢
从高中数学里函数增长的快慢我们很容易理解，当n足够大的时候，指数时间算法的步数计算机已经撑不住哩~ 阶乘更不用说
nkn^knk显然比kn（k≠1）k^n（k \not=1）kn（k=1）增长的慢的多。
我们把各个时间拉一张表出来：
函数类型
示例（n=10）
示例（n=30）
示例（n=50）
实际可行性
常数时间
10
线性时间（n）
10
线性对数时间(nlogn)
多项式时间（n3n^3n3）
1000
指数时间（2n2^n2n）
10 ...
z
这是一个大家或多或少都听过的名词——“伪随机”
极致省流的来讲，计算机的确定性使得计算机中不存在真正的“随机”机制
计算机的确定性
计算机是一个确定性系统，它的所有操作都是遵循预设的指令来进行的，也就是说它的输出只由输入和初始状态决定，一套输入和初始状态，只能对应一个输出值。
也正是因为这种确定性，我们才会使用计算机进行极大规模的运算而不担心它出错。
伪随机数怎么产生的
我记得刚开始上python，有一题是这么出的
答案：
1234567891011import randomdef code(seed): random.seed(int(seed)) lst = "ABCDEFGHIJ0123456789" p = '' for i in range(6): c = random.choice(lst) p += c return pn = int(input())print(code(n))
当时做到这里其实很疑惑的
啥叫种子啊
为什么种子是5，输出出来的就一定是"9I1 ...
在ECC中，Pohlig-Hellman攻击可以用来降低特定情况下的离散对数问题的求解难度。
我们知道想要破解ECC最大的难题是ECDLP，即椭圆曲线离散对数问题
假设我们已经知道了椭圆曲线上的基点G和公钥Q，想要从Q=kG中求解私钥k目前没有找到比朴素算法更优的解决方案
我在学习这块内容的时候突然有了个疑惑（之前完全没意识到，好奇怪），就是为什么椭圆曲线加密使用的是Q = kG，却被称作离散对数问题？对数在哪？这不就是看起来很普通的乘法吗？
那我们就先跳出椭圆曲线，先来研究有限域乘法群
设在有限域FP∗设在\color{blue}有限域\mathbb{F}_P^{*}设在有限域FP∗，定义运算*为模p乘法，在该有限域中存在生成元g，使得h=gkmod ph=g^k\mod{p}h=gkmodp，离散对数就是已知h和g求解k的过程。这样显然k的表达式会出现对数，且由于运算进行在有限群中，所以称为离散对数
上面h=gkmod ph=g^k\mod{p}h=gkmodp，显然可以写为h=g∗g∗g+....mod ph = g*g*g+....\mod{p}h=g∗g∗g+... ...
