ECC

ECC简介

大体上的意思是说，给你一个曲线F
y^2=x^3+ax+b
你确定下来a和b，然后找一个在曲线F上的点G（x1,y1）
然后自己随机生成一个k（私钥）
然后生成公钥
S=kG
注意，这里的kG可不是k*G这么简单，这是几何意义上的：
S=G+G+G+G+……+G（K个G）
然后把公钥丢出去，私钥留给自己,和RSA差不多啦,重点应该是在于如何求S

1	G（x1,y1）,P（x2,y2）

重点来了：核心公式

x3≡t^2-x1-x2(mod p)
y3≡t(x1-x3)-y1(mod p)
其中
若P=G 则 t=(3x^2+a)/2y1 
若P≠G 则 t=(y2-y1)/(x2-x1)

故此可以求出公钥S,为什么这个算法安全呢？你自己试试能不能逆运算就知道了

ECC题目分析

题目介绍

已知椭圆曲线加密Ep(a,b)参数为
p = 15424654874903
a = 16546484
b = 4548674875
G(6478678675,5636379357093)
私钥为
k = 546768
求公钥K(x,y)
提示：K=kG
提交格式XUSTCTF{x+y}(注意，大括号里面是x和y加起来求和，不是用加号连接)

exp

# -*- coding:utf8 -*-
def egcd(t, b):
    if t == 0:
      return (b, 0, 1)
    else:
      g, y, x = egcd(b % t, t)
      return (g, x - (b // t) * y, y)
def modinv(o, m):
    g, x, y = egcd(o, m)
    if g != 1:
      raise Exception('modular inverse does not exist')
    else:
      return x % m
def ecc_m(x1,y1,x2,y2):
    if ((x1 == x2) & (y1 == y2)):
        fenzi=3*x1*x1+a
        fenmu=2*y1
    else:
        fenzi = y2 - y1
        fenmu = x2 - x1
    m=(abs(fenzi) * modinv(abs(fenmu), p)) % p
    if ((fenzi >= 0 & fenmu >= 0) | (fenzi < 0 & fenmu < 0)):
        return m
    else:
        return p - m
def ecc_x(x1,x2,m):
    result_x = m*m-x1-x2
    if result_x>0:
        return result_x%p
    else:
        p1=p
        if abs(result_x)>p1:
            shang=abs(result_x)/p
            p1=shang*p+p
        return p1+result_x
def ecc_y(x1,result_x,y1,m):
    result_y = m*(x1-result_x)-y1
    if result_y>0:
        return result_y%p
    else:
        p1 = p
        if abs(result_y) > p1:
            shang = abs(result_y) / p
            p1 = shang * p + p
        return p1 + result_y
def ecc_result_x(x1,y1,x2,y2):
    m = ecc_m(x1,y1,x2,y2)
    result_x=ecc_x(x1,x2,m)
    return result_x
def ecc_result_y(x1,y1,x2,y2):
    m = ecc_m(x1,y1,x2,y2)
    result_x = ecc_x(x1, x2, m)
    result_y=ecc_y(x1, result_x, y1, m)
    return result_y
a=16546484
p=15424654874903
x1=x2=x3=6478678675
y1=y2=5636379357093
n=546767
while(n>0):
    x2=ecc_result_x(x1,y1,x2,y2)
    y2=ecc_result_y(x1,y1,x3,y2)
    x3=x2
    n-=1
print x2,y2
result = x2+y2
flag = "XUSTCTF{%s}"%result
print flag

ASE的实现

ASE的加密处理是字节为单位。

公式

1 2	C=E(K,M) M=D(K,C)

其中M为明文，K为秘钥，C为密文,E为加密函数，D为解密函数，对称加密(分组密码)。

秘钥扩展

秘钥长度可以使用128位，192位，256位(不同的秘钥，加密轮数也不同，10次，12次，14次)。这里以128位(也就是16个字节)作为例子，将128位长度的字符串读进一个4*4的整数数组中。
如将0123456789abcdef作为明文。分别记为P0=0,P1=1,P2=2,…P15=f。

解密加密过程

上图也展示了AES解密过程，解密过程仍为10轮，每一轮的操作是加密操作的逆操作。由于AES的4个轮操作都是可逆的，因此，解密操作的一轮就是顺序执行逆行移位、逆字节代换、轮密钥加和逆列混合。同加密操作类似，最后一轮不执行逆列混合，在第1轮解密之前，要执行1次密钥加操作。

下面分别介绍AES中一轮的4个操作阶段，这4分操作阶段使输入位得到充分的混淆。

字节代换

加密
AES的字节代换其实就是一个简单的查表操作。AES定义了一个S盒和一个逆S盒。
S盒

如将0x12将S盒1作为行，2作为列。找到位置对应的数0xc9,替换x012。

解密
逆S盒

行移位

加密
行移位是一个简单的左循环移位操作。如下:
状态矩阵
第0行左移0字节
第1行左移1字节
第2行左移2字节
第3行左移3字节，

解密
行移位是一个简单的右循环移位操作

列混合

加密
列混合变换是通过矩阵相乘来实现的，经行移位后的状态矩阵与固定矩阵(要求可逆)相乘，得到混合后的状态矩阵。

解密
通过逆矩阵可以求

轮密钥加

加密
轮密钥加是将128位轮密钥Ki与经过列混合状态矩阵中的数据进行逐位异或操作，如下图所示。其中，密钥Ki中每个字W[4i],W[4i+1],W[4i+2],W[4i+3]为32位比特字，包含4个字节，他们的生成算法下面在下面介绍。轮密钥加过程可以看成是字逐位异或的结果，也可以看成字节级别或者位级别的操作。也就是说，可以看成S0 S1 S2 S3 组成的32位字与W[4i]的异或运算。

解密
轮密钥加的逆运算同正向的轮密钥加运算完全一致，这是因为异或的逆操作是其自身。轮密钥加非常简单，但却能够影响S数组中的每一位。

秘钥扩展
AES首先将初始密钥输入到一个44的状态矩阵中
这个44矩阵的每一列的4个字节组成一个字，矩阵4列的4个字依次命名为W[0]、W[1]、W[2]和W[3]，它们构成一个以字为单位的数组W。例如，设密钥K为”abcdefghijklmnop”,则K0 = ‘a’,K1 = ‘b’, K2 = ‘c’,K3 = ‘d’,W[0] = “abcd”。
接着，对W数组扩充40个新列，构成总共44列的扩展密钥数组。新列以如下的递归方式产生：
1.如果i不是4的倍数，那么第i列由如下等式确定：
W[i]=W[i-4]⨁W[i-1]
2.如果i是4的倍数，那么第i列由如下等式确定：
W[i]=W[i-4]⨁T(W[i-1])
其中，T是一个有点复杂的函数。
函数T由3部分组成：字循环、字节代换和轮常量异或，这3部分的作用分别如下。
a.字循环：将1个字中的4个字节循环左移1个字节。即将输入字[b0, b1, b2, b3]变换成[b1,b2,b3,b0]。
b.字节代换：对字循环的结果使用S盒进行字节代换。
c.轮常量异或：将前两步的结果同轮常量Rcon[j]进行异或，其中j表示轮数。

代码

liunx编译
gcc -m32 -no-pie -o aes aes.c main.c
链接：
https://pan.baidu.com/s/1Ft8rCFmrw7OHiBcAjaskgQ
密码：
kqkv

参考:
https://blog.csdn.net/qq_28205153/article/details/55798628