基点p就是最初选定的那个点
1和2都是整数集合，但是1/2=0.5就不属于整数集合
一直加，一直乘，还能保证有限个数字？这是因为采用了取模的运算，让元素始终都在有限的范围内。
如何计算分数求模？
设n=1/2mod23,那么n和1/2mod23是同余的。而后两边同时乘2，就可以得到下面的内容。
负数求模的算法
进而计算出2A的坐标，从而计算出3A,4A等等。
但是k那么大，这样计算岂不是很麻烦？
这时候我们就有了下面的计算方法
注意：这里算出二进制后，将其反转，也就是10010111反转一下是11101001 ，后面也就有了2^0+2^1+2^2+2^4+2^7
先算出A，然后取A的2倍，得到2A，而后2A+A,而后在2A的基础上再取2倍得到4A，而后再将A+2A+4A,再将4A取2倍，得到8A,那么就是A+2A+4A+8A,依次类推。这就是倍数加法运算。
例题：攻防世界：easy_ecc
附件内容
有p,a,b的数值，就可以知道这个椭圆曲线就是
y=x^3+ax+b=x^3+16546484x+4548674875 出发点G是(6478674857,5636379357093)
那么公钥我们设置为Q=k(x,y)=kG
先将K=546768进行二进制，二进制计算遵循原则：为从低位到高位依次处理二进制位，若位为0，则将当前点加倍；若位为1，则将当前点加倍后再与基点相加。
计算2A(只给了一个基点G，可以看出是A=B的类型)，使用方法，即是公式：
解法1：脚本语言
class point: def __init__(self, x, y): self.x = x self.y = y class ell: def __init__(self, p, a, b): self.p = p self.a = a self.b = b def add(self, pA, pB): if pA.x == pB.x and pA.y == pB.y: k = mod((3 * (pA.x * pA.x) + self.a), (2 * pA.y), self.p) else: k = mod((pB.y - pA.y), (pB.x - pA.x), self.p) rx = k * k - pA.x - pB.x rx = rx % self.p ry = k * (pA.x - rx) - pA.y ry = ry % self.p R = point(rx, ry) return R def ne(self, n, G): s = str(bin(n)[::-1]) print(s) sumG = None addPoint = G for i in range(len(s)): if s[i] == '1': if sumG is None: sumG = addPoint else: #此处是用来计算SUMG的累加和 sumG = self.add(sumG, addPoint) #无论是0还是1都加一次 addPoint = self.add(addPoint, addPoint) return sumG def mod(a, b, p): \# a/b mod p if b < 0: b = -b a = -a return (a % p * pow(b, p - 2, p)) % p p = 15424654874903 a = 16546484 b = 4548674875 ep = ell(p, a, b) G = point(6478678675, 5636379357093) k = 546768 flag = ep.ne(k, G) print(flag.x + flag.y) cyberpeace{19477226185390}
解释一下代码：
初始化 __init__：用于初始化新创建的对象。 class point: def __init__(self, x, y): self.x = x self.y = y 这里是定义了一个点，将传入的点（x,y)赋值给self.x和self.y 核心关键 class ell: def __init__(self, p, a, b): self.p = p self.a = a self.b = b def add(self, pA, pB): if pA.x == pB.x and pA.y == pB.y: k = mod((3 * (pA.x * pA.x) + self.a), (2 * pA.y), self.p) else: k = mod((pB.y - pA.y), (pB.x - pA.x), self.p) rx = k * k - pA.x - pB.x rx = rx % self.p ry = k * (pA.x - rx) - pA.y ry = ry % self.p R = point(rx, ry) return R def ne(self, n, G): s = str(bin(n)[::-1]) 10010111 -- 11101001 print(s) sumG = None addPoint = G for i in range(len(s)): 1 1 1 0 1 0 0 1 if s[i] == '1': if sumG is None: sumG = addPoint sumG:G else: #此处是用来计算SUMG的累加和 sumG = self.add(sumG, addPoint) G+2G=3G 3G+4G=7G 7G+16G=23G 23G+128G=151G #无论是0还是1都自己加一次自己 addPoint = self.add(addPoint, addPoint) 2G 2G+2G=4G 4G+4G=8G 16G 32G 64G 128G 256G return sumG 这里是定义了一个类ell，来完成一些列的操作。一点一点的看 def __init__(self, p, a, b): self.p = p self.a = a self.b = b 初始化我们输入的p，a,b的数值。 下面有个问题：这里的G点，也就是基点，到底是如何传进去的呢？ def add(self, pA, pB): if pA.x == pB.x and pA.y == pB.y: k = mod((3 * (pA.x * pA.x) + self.a), (2 * pA.y), self.p) else: k = mod((pB.y - pA.y), (pB.x - pA.x), self.p) rx = k * k - pA.x - pB.x rx = rx % self.p ry = k * (pA.x - rx) - pA.y ry = ry % self.p R = point(rx, ry) return R 定义了一个加法规则，传入A,B两个点 if pA.x == pB.x and pA.y == pB.y: 如果A点和B点相同，也就是我们上面说的A=B的情况 k = mod((3 * (pA.x * pA.x) + self.a), (2 * pA.y), self.p)
计算出k的数值，这里的mod方法使用的是后面定义的mod的计算方法
def mod(a, b, p): \# a/b mod p if b < 0: b = -b a = -a #pow() 函数用于计算 b 的 p - 2 次幂并取模 p return (a % p * pow(b, p - 2, p)) % p
这个Python函数mod(a, b, p)执行以下操作：实现a/b对模p进行计算。 检查除数的符号：如果b小于0，函数会将b和a都取其相反数。这是因为模运算中除数可以是负数，但在这个函数中，我们将其转换为正数以简化计算。 使用模逆元计算：函数使用了费马小定理的一个应用，即对于质数p，如果b与p互质（即它们的最大公约数为1），那么存在一个数x（即b^(p-2) % p），使得bx % p = 1。这个x被称为b关于模p的逆元。 计算模运算：通过(a % p) * (b^(p-2) % p)，函数实现了a / b对模p的计算。这是因为a / b等价于a * (b^(-1))，而b^(-1)就是上面找到的模逆元。 最终取模：为了确保结果在0到p-1之间，函数对结果再次取模p。 总结来说，这个函数计算了a/b对模p的结果，其中b和p都是正整数，且p通常是一个质数，用于加密算法或者在有限域中进行计算。
else: k = mod((pB.y - pA.y), (pB.x - pA.x), self.p) 如果A，B两点不相同，执行上面的方法计算K rx = k * k - pA.x - pB.x rx = rx % self.p ry = k * (pA.x - rx) - pA.y ry = ry % self.p R = point(rx, ry) return R 得出K后，计算x和y的值，并返回这个坐标 def ne(self, n, G): s = str(bin(n)[::-1]) print(s) sumG = None addPoint = G for i in range(len(s)): if s[i] == '1': if sumG is None: sumG = addPoint else: sumG = self.add(sumG, addPoint) addPoint = self.add(addPoint, addPoint) return sumG 推算出公钥Q，使用的就是倍数加法运算，将私钥K，代码里是n,k后面我们可以传入。 s = str(bin(n)[::-1]) print(s) 将n转换为二进制字符串，并反转字符串，并输出一下s的数值。 sumG = None 设置sumG的初始值为空 addPoint = G 将输入的基点赋值给addPoint #循环遍历逆向输出的二进制数字 for i in range(len(s)): #如果二进制数字是1 if s[i] == '1': #如果sumG还是空值的话 if sumG is None: #将addPoint的数值赋予给sumG sumG = addPoint #sumG不是空数值的话 else: #执行自加，这个函数的功能是将addPoint加到sumG上，并将结果赋值给sumG sumG = self.add(sumG, addPoint) #在每次循环中，无论当前位是 '1' 还是 '0'，都使用 add 函数将 addPoint 自身相加一次（即 addPoint = self.add(addPoint, addPoint)），模拟点的倍增过程。 addPoint = self.add(addPoint, addPoint)
add 函数 功能说明：此函数实现的是椭圆曲线密码学中点的加法运算。给定椭圆曲线上两点 pA 和 pB，以及椭圆曲线方程的一些参数（隐含在类的属性中，如 self.a, self.p），计算这两点的和 R，结果同样位于同一条椭圆曲线上。 步骤分解： 判断特殊情况：首先检查 pA 和 pB 是否为同一点。如果是（即它们的坐标相同），根据椭圆曲线点加倍的公式计算斜率 k。公式为：[k = \text{mod}((3 \times (pA.x^2) + self.a), (2 \times pA.y), self.p)]。这里利用模运算保持结果在模 self.p 下。 常规情况处理：如果 pA 和 pB 不是同一个点，则按照点的加法规则计算斜率 k，公式为：[k = \text{mod}((pB.y - pA.y), (pB.x - pA.x), self.p)]。这同样确保了结果的正确性且在模意义下。 计算新点坐标： 根据 k 计算新点的 x 坐标 rx：[rx = k^2 - pA.x - pB.x]，并取模 self.p 以确保结果落在期望的范围内。 接着计算 y 坐标 ry：[ry = k \times (pA.x - rx) - pA.y]，同样对结果取模 self.p。 构造并返回新点：最后，使用计算出的 rx 和 ry 创建一个新的点 R 并返回。 ne 函数 功能说明：此函数实现了在椭圆曲线上通过多次点加操作计算一个点乘（即点 G 重复相加 n 次）的结果。这是椭圆曲线加密算法中的关键步骤，用于高效地计算大指数幂的点表示。 步骤分解： 转换整数为二进制：将输入的整数 n 转换为二进制字符串 s，并反转字符串以便从最低位开始处理。 初始化变量：设置 sumG 初始化为 None，表示累加结果的初始状态；addPoint 初始化为给定点 G，作为每次迭代中用于加法操作的基础点。 遍历二进制字符串：从最低位到最高位遍历二进制字符串 s 的每个字符。 对于遇到的每一个 '1'，执行以下操作： 如果 sumG 仍为 None，则将其设为 addPoint。 否则，使用 add 函数将 sumG 与 addPoint 相加，并更新 sumG 为结果。 在每次循环中，无论当前位是 '1' 还是 '0'，都使用 add 函数将 addPoint 自身相加一次（即 addPoint = self.add(addPoint, addPoint)），模拟点的倍增过程。 返回结果：遍历结束后，sumG 即为点 G 乘以 n 的结果，在椭圆曲线上的表示，最终返回 sumG。 综上，这两个函数共同实现了椭圆曲线上的点加法和点乘运算，是椭圆曲线密码学中的基础算子。
解法2：工具:ECCTOOL
最后将Rx和Ry的数值相加就是flag
