타원 곡선 암호화 파이톤의 실현 2 (타원 곡선과 ECDSA)

거부

이 글은 Software Design 2022년 3월호의'제4장: 전자 서명을 체험하는 과정, 파이톤이 타원 곡선 비밀번호를 실시한다'는 기고문으로 기술평론회사가 호의로 공개했다.
원래 LaTex였던 것을 표시로 수정하여 두 부분으로 나누다.
전반전은 타원 곡선 암호 Pythhon의 실현 중 하나 (유한체와 ECDH 키 공유)였다.
문장의 견본 코드는 지원 페이지에서 다운로드할 수 있다.

타원 곡선류

타원 커브의 점

유한체 클래스를 설치할 수 있으므로 타원 곡선 클래스\text{Ec}를 설치합니다.
타원 곡선은 유한체\text{Fp} 및 해당 값 a 및 b에 의해 결정됩니다.
타원 곡선류는 타원 곡선절에 소개된 r개 점 0, P, 2P...집합하다.
secp256k1은 TLS 또는 비트코인에 사용되는 타원 곡선의 매개 변수입니다.
a=0
b=7
p=2^{256} - 2^{32} - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1
r=\text{0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141}
SEC 2: Recommended Elliptic Curve Domain Parameters.
클래스 방법\text{init}을 사용하여 이러한 값을 설정합니다.

class Ec:
    @classmethod
    def init(cls, a, b, r):
        cls.a = a
        cls.b = b
        cls.r = r

Ec::init
타원 곡선의 점은 2개의\text{Fp} 요소로 표시할 수 있습니다.P=(x,y).그러나 O는 정수 0에 해당하는 특별한 점(나중에 0으로 표시)으로 분류해야 한다.
이에 따라 멤버 변수로 x, y 외에 0 여부를 나타내는 시그니처 isZero도 준비했다.
(x, y)방정식 y^2 = x^3+ax+b를 충족해야 합니다.
값이 올바른지\text{isValid} 확인하는 방법을 준비하십시오.iszero가 트루일 때 트루입니다.

def isValid(self):
    if self.isZero:
        return True
    a = self.a
    b = self.b
    x = self.x
    y = self.y
    return y*y == (x*x+a)*x+b

Ec::isValid

타원 커브의 점 계산하기

타원 곡선점의 덧셈과 뺄셈 규칙을 소개하다.
먼저 점 0과 임의의 점 P에 대해 P+0 = 0+P = P를 설정합니다.
또한 P=(x1, y1)일 경우 -P=(x1, -y1)로 정의됩니다.점의 음수는 y 좌표 값을 반전시키는 기호입니다.
P와 -P는 일반적으로 0입니다.P+(-P)=0.
그리고 일반점 P=(x1, y1)과 Q=(x2, y2), R=(x3, y3)=P+Q를 다음과 같이 계산한다.

덧셈 공식
공식은 복잡하지만 네 가지 계산만 있기 때문에 유한체절이 실현된 유한체로 계산할 수 있다.
왜 이런 의식이 나왔는지에 관해서는 졸저《구름을 지탱하는 앞으로의 암호 기술》 등을 참조하십시오.
이 공식을 Python으로 직접 구현합니다.

def __add__(self, rhs):
    if self.isZero:
        return rhs
    if rhs.isZero:
        return self
    x1 = self.x
    y1 = self.y
    x2 = rhs.x
    y2 = rhs.y
    if x1 == x2:
        # P + (-P) = 0
        if y1 == -y2:
            return Ec()
        # dbl
        L = x1 * x1
        L = (L + L + L + self.a) / (y1 + y1)
    else:
        L = (y1 - y2) / (x1 - x2)
    x3 = L * L - (x1 + x2)
    y3 = L * (x1 - x3) - y1
    return Ec(x3, y3, False)

Ec::add

타원 곡선점의 정수 배

마지막으로 타원 곡선점의 정수 배를 실현한다.
2P=P+P, 3P=2P+P, 4P=3P+P로 차례로 n배의 P를 구한다면 n이 256비트 정수라면 우주 멸망도 끝나지 않는다.
효율적인 방법을 소개합니다.
n = 11 = 0b 1011 (바이너리 표시) 이면 0b 1011 = 0b 1010 +1 = (2\times 0b101) +1
Q=0b1011 P =(2\times 0b101 + 1)P = 2(0b101 P) + P
을 입력합니다.이어서 0b101P에 대해 같은 일을 반복적으로 반복한다면
Q=2(0b101 P) + P =2(2 (0b10 P) + P) + P = 2(2 (2 P) + P) + P
즉, n이 2진법으로 표시될 때 P의 상위 k위를 배로 구하면
이 값을 배로 하고 다음 비트가 1이면 P를 더하면 k+1비트의 배를 얻어 중복할 수 있다.
이 방법에서 순환 횟수는 n의 비트 길이이기 때문에 256자리 정수라도 최대 256번의 순환이 완성된다.
Pythn을 사용하려면 먼저\text{bin(n)}로 n의 이진수를 표시하고text{0b...}처음 두 문자는 0과 1로 구성된 문자열로 순환됩니다.

def __mul__(self, rhs):
    if rhs == 0:
        return Ec()
    bs = bin(rhs)[2:]
    ret = Ec()
    for b in bs:
        ret += ret
        if b == '1':
            ret += self
    return ret

Ec::mul
ECDH 키 공유에 필요한 메소드 설치가 완료되었습니다.

ECDSA의 실현

마지막으로 타원 커브의 서명 중 하나인 ECDSA를 사용하여 구현합니다.

서명 요약

서명은 키 생성, 서명, 검사 세 가지 알고리즘으로 구성되어 있다.
키를 생성할 때, 앨리스는 서명 키 s와 인증서 키 S를 생성합니다.서명 키 s는 자신만의 비밀 값이기 때문에 기밀 키, 검증기 키 S는 다른 사람에게 사용되는 키이기 때문에 공개 키라고도 부른다.
sign은 서명하고자 하는 데이터 m에 서명 키 s로 서명한 데이터σ탭
secp 256k1 곡선의 경우 256비트 정수 2개로 구성된 512비트 고정 길이 데이터입니다.

서명하다.
데이터 m 및 서명σ한 쌍을 다른 사람에게 주다.
밥은 인증 키 S(m,σ)의 정확성, 수용 또는 거절.

ECDSA 키 생성

ECDSA의 키 생성 알고리즘은 다음과 같습니다.
우선 앨리스는 서명 키로\text {Fr}에서 무작위 수 s를 가져옵니다.
그런 다음 점 P에 s의 S=sP를 곱하여 인증 키로 사용합니다.ECDLP의 어려움으로 인해 인증서 키에서 서명 키를 얻을 수 없습니다.

ECDSA

P = initSecp256k1()
s = Fr()
s.setRand() # 署名鍵
S = P * s   # 検証鍵

키 생성

ECDSA 서명

해싱 함수를 사용하여 서명하고 검증합니다.산열 함수 자체의 설명은 다른 책에 넘겨질 것이다.
Python에서 SHA-256을 사용하는 경우 hashlib을 삽입합니다.
해시 값은 256자리이고, 파이톤은 32바이트로 배열되어 있다.
유한체\text{Fr}의 값으로 간주할 때, 그룹의 시작은 정수 상위의 큰 endian으로 정수로 변합니다.
예를 들어\text{b'{textbackslash}×12{textbackslash}×34'}는\text{0x1234}이다.
msgToFr (그림의 h) 는 메시지 m에서\text{Fr}까지의 함수입니다.

import hashlib
def byteToFr(b):
    v = 0
    for x in b:
        v = v * 256 + x
    return Fr(v)

def msgToFr(msg):
    H = hashlib.sha256()
    H.update(msg)
    return byteToFr(H.digest())

산열값의 정수
데이터 m의 서명을 만들려면 무작위 k 를 선택하십시오.
그런 다음 타원 커브의 점 kP를 계산하여 x 좌표를 r로 설정합니다.
\sigma=(r,(h(m)+sr)/k)는 서명입니다.여기에 덧셈과 나눗셈은 유한체\text{Fr}를 사용하여 계산합니다.
타원 곡선의 점을 계산할 때는 소수p의 유한체를 사용하지만 서명할 때는 타원 곡선의 점의 개수 r의 유한체를 사용한다.
\text{Fp}과\text{Fr}는 소수가 다른 반일 뿐이다.
어떻게 설치해야 할지 고민이 많았지만, 여기서\text{fp.py}를 간단하게 복사해서\text{fr.py}를 만들었고, 학급 이름을 바꿨습니다.

def sign(P, s, msg):
    z = msgToFr(msg)
    k = Fr()
    k.setRand()
    Q = P * k
    r = Fr(Q.x.v)
    return (r, (r * s + z) / k)

서명

서명에 사용되는 무작위 수

\text{sign}에서 사용하는 k는 무작위 수를 올바르게 생성해야 합니다.
2010년 플레이스테이션3의 서명 설치는 같은 무작위 수를 사용했기 때문에 서명 키 누출의 취약성Console Hacking 2010 PS3 Epic Fail이 발견됐다.
무작위 수를 생성하는 것은 매우 번거롭기 때문에 서명 키와 데이터 등 k를 생성하는 알고리즘RFC6979으로 대체한다.
관심 있으신 분들은 보세요.

ECDSA 인증

마지막으로verify를 실시합니다.
verify에서 데이터 m과 서명\sigma=(r,t)을 줄 때 먼저\text{z=msgToFr(msg)}를 계산합니다.
그런 다음 타원 커브의 점 R=(zP+rS)/t를 계산합니다.
t로 타원 곡선의 점을 제거하는 작업은 유한체\text{Fr}에 곱하기 w=1/t와 같다.
R=(z P + rS)\times w
타원 곡선의 정수 배는 유한체의 곱셈보다 훨씬 무거워서 R=(zw) P+(rw) S가 되면 빨라진다.

def verify(P, sig, S, msg):
    (r, t) = sig
    if r == 0 || t == 0:
        return False
    z = msgToFr(msg)
    w = Fr(1) / t
    u1 = z * w
    u2 = r * w
    Q = P * u1 + S * u2
    if Q.isZero:
        return False
    x = Fr(Q.x.v)
    return r == x

검증
마지막으로 구한 타원 곡선의 점 Q의 x 좌표가 r와 같으면\text{True}를 되돌려줍니다.
이상은 ECDSA의 실현입니다.
실제로 사용하면 더욱 엄격한 검사, 검증 키와 서명 데이터의 양식을 서로 활용하는 데 사용되는 등 실시해야 할 부분이 있지만 숫자를 확인하면서 조작하기에는 충분하다.
이 글은 타원 곡선, 키 공유, 서명 이해에 도움이 되었으면 합니다.