ECDSA (타원 곡선 디지털 서명 알고리즘)

ecdsa (elliptic curve digital signature algorithm)

실제 업무와 생활에서 우리는 서명으로 문서에 대한 승인을 표현하고, 다른 사람들은 당신의 서명을 인식하고 당신의 서명을 위조할 수 없습니다. 디지털 서명은 디스플레이 서명의 전자 구현으로 실제 서명의 특징을 완전히 달성할 수 있을 뿐만 아니라 더 잘할 수도 있습니다.

일반적으로 사용되는 디지털 서명 알고리즘으로는 RSA (rivest-sha mir-ad leman scheme), DSS(Digital Signature Standard) 등이 있습니다. 비트코인은 ECDSA 를 사용하여 계정의 공용 키를 생성하고 거래 및 블록을 확인합니다.

1.Alice (암호학에서 A ~ Z 로 시작하는 인명이 갑을 병정 대신 쓰이며, 글자가 뒤처질수록 빈도가 낮아짐) 한 쌍의 키를 생성합니다. 하나는 sk(signing key) 로 비공개입니다. 다른 하나는 vk(verification key) 입니다. 공개됩니다. < P > 이 키 쌍은 동시에 생성되며 수학적으로 상호 연관되어 있으며 vk 에 따라 sk 에 대한 어떠한 정보도 추측할 수 없습니다.

2. 디지털 서명 알고리즘은 정보 M 과 sk, 디지털 서명 생성 Sm

3. 검증 함수가 정보 M, Sm 및 vk 를 입력으로 수신하면 yes 또는 no 를 반환합니다. 이 단계의 목적은 정보 M 에 대해 본 디지털 서명이 실제로 Alice 의 sk 에 의해 발급되어 정보가 서명과 일치하는지 확인하는 것입니다. < P > 자필 서명과 달리 자필 서명은 기본적으로 비슷하지만 디지털 서명은 입력의 영향을 많이 받습니다. 입력에 약간의 변화가 있으면 완전히 다른 디지털 서명이 생성됩니다. 일반적으로 정보는 직접 디지털 서명되지 않고 정보의 해시 값에 서명됩니다. 암호화 해시 함수의 무충돌성으로 알 수 있어 원본 정보에 서명하는 것만큼 안전합니다.

수학적으로 다음 방정식을 충족하는 점에 의해 형성된 곡선을 임의 타원 곡선이라고 하며 a 와 b 는 임의의 값이 될 수 있습니다. 다음은 임의 타원 함수의 몇 가지 예입니다.

는 통과 방법을 알고 있습니다 Secp256k1 타원 곡선을 기반으로 하는 ECDSA 알고리즘이 공용 키를 생성하기 전에 임의 타원 곡선에서 점 추가가 어떻게 이루어지는지 알아야 합니다.

먼저 타원 곡선 위의 점 덧셈을 정의합니다. 타원 곡선에 두 점, a 와 b 점이 있으면 이 두 점을 지나는 선이 곡선과 세 번째 점 (c 점) 에서 교차한 다음 x 축에 대해 대칭으로 d 점을 얻으면 d 는 두 점의 합으로 D=A+BD=A+BD=A+B 로 기록됩니다. 분명히 D 점도 이 곡선에 있습니다. 따라서 타원 곡선에 있는 두 점의 합도 곡선 위의 점입니다.

예외:

1. 두 점이 일치하면 곡선의 교차점과의 대칭점이 합인 점의 접선이 됩니다. 즉, A+A=C

그림:

가 덧셈을 한 후 곱셈 구현은 여러 번 덧셈을 하는 것에 불과합니다. 기준점 P 가 있으면 곱셈을 할 수 있고, 결국 곡선의 다른 점을 얻을 수 있습니다. < P > PPP 를 타원 곡선의 점으로 설정하면 양의 정수 KK 에 점 PPP 를 곱한 결과는 다음 방정식에 의해 정의됩니다. 표현식의 덧셈은 위에서 언급한 타원 곡선의 점 덧셈입니다. < P > 점의 연산은 결합법을 만족시킵니다. < P > 분명히 누적을 통한 계산은 어리석은 방법이며 시간 복잡성은 다음과 같습니다. 위에서 언급했듯이 타원 곡선에 있는 점의 추가는 결합법을 만족시키는 것입니다. 즉, 확장하면

가 있기 때문에 계산과 같은 사오 작업이 있습니다. 먼저 계산할 수 있습니다. 그런 다음 계산합니다. 다시 계산하다 마지막 계산. 여기서 우리는 15 번의 덧셈을 4 번으로 줄였다.

물론 k 의 값이 항상 2 의 거듭제곱일 수는 없습니다. 실제로 위의 작업은 K 가 임의의 양의 정수인 경우로 확대될 수 있습니다. 예를 들어 23P 를 계산하면 먼저 계산한 다음 < P > 를 계산합니다. 총 * * * 7 번만 더하면 됩니다. < P > 분석, 모든 양의 정수 K 에 대해 이 방법을 사용하여 K 를 계산할 수 있습니까? P 에 필요한 덧셈 계산 횟수를 < P > 로 줄이면 시간 복잡도의 관점에서 볼 때 이 알고리즘은 하나의 알고리즘입니다. < P > 이 방법을 고속 전력 알고리즘이라고 하며, 원래 특정 수의 K 제곱을 빠르게 계산하는 데 사용되었으며, 여기서는 타원 곡선 점 곱셈의 빠른 계산으로 확대됩니다. < P > 타원 곡선의 점 곱셈을 소개한 후 갑자기 빠른 전력 알고리즘이 나타나는 이유는 무엇입니까? 타원 곡선 암호화에 대한 빠른 전력 알고리즘의 의미는 무엇입니까? 수학자/암호학자들은 빠른 전력 알고리즘을 이용하여 계산한 시간의 복잡성이 대수급이라는 것을 발견했지만, 합을 알고 있는 전제하에 거꾸로 내놓은 값은 시도된 값보다 훨씬 빠른 알고리즘이 없다는 것을 알게 되었기 때문이다. (윌리엄 셰익스피어, 윈스턴, 과학명언) 그래서 타원 곡선 암호화에 의존하는 수학 문제가 이렇게 탄생했다. < P > 타원 곡선에 있는 점의 덧셈을 곱하는 표기법을 바꾸면 원래의 곱셈이 전력 연산이 된다면, 위의 난제의 형식은 이산대수 문제와 일치해야 한다. 즉, < P > 그래서 이 난제는 타원 곡선의 이산대수 문제라고 합니다.

두 형식이 일치하더라도 동등하지 않습니다. 사실, 이 문제는 큰 정수 계수 분해 (RSA) 와 이산 대수 (DH) 문제보다 훨씬 어렵습니다. 현재 하위 지수 시간 복잡도의 알고리즘 (큰 정수 계수 분해와 이산대수 문제가 모두 있음) 이 없기 때문에 같은 보안 강도에서 타원 곡선 암호화의 키는 RSA 와 DH 보다 훨씬 짧습니다. 이것은 타원 곡선 암호화의 큰 이점입니다. < P > 는 ~ 비트 사이의 값 X 를 무작위로 취한다고 가정하고, 최종 결과는 반드시 곡선의 한 점에 떨어질 것이라고 가정합니다. 이 점이 공개적이고 구체적인 곡선의 방정식인 경우 원래의 무작위 값을 반출할 수 있다고 가정해 봅시다. < P > 증명: 찾는 과정은 폭력을 통해서만 계산할 수 있으며, 가능한 값은 ~ 중 하나이며, 평균적으로 한 번에 한 번 값을 찾을 수 있도록 계산해야 한다. 그렇다면 문제가 생겼습니다. 한 번의 계산을 실행하는 데 얼마나 걸립니까? < P > 우주가 탄생한 순간부터 현재까지 1 조 번의 연산을 할 수 있는 슈퍼컴퓨터를 사용한다고 가정해 봅시다. 값을 찾을 확률은 입니다. 이 확률은 다음 초에 지구가 거대한 운석에 부딪혀 파괴될 확률과 비슷하다. 우리가 이곳을 읽었기 때문에 이 일은 일어나지 않았다는 것을 보여준다. (알버트 아인슈타인, Northern Exposure (미국 TV 드라마), 성공명언) < P > 위의 경우 ~ 비트의 난수로 개인키로 사용할 수 있습니다. 임의 타원 곡선의 한 점, 즉 개인 키로 생성된 공개 키이므로 장점은 1 로 증명할 수 있습니다. < P > 그러나 암호학에서는 위에서 설명한 실수 필드의 타원 곡선을 사용할 수 없습니다.

때문에 유한 필드에 타원 곡선을 도입해야 합니다. < P > 장점 2 를 증명하기 위해 임의 타원 곡선을 약간 변경해야 합니다. 마지막으로 계산된 점의 좌표값을 512 비트로 추가하기 위해 secp256k1 은 소수를 모델링하는 메커니즘을 도입했습니다. 특히 임의 타원 곡선이 < P > 에서 < P > 로 변경되어 보다 작은 최대 소수입니다. < P > 이 시점에서 임의 타원 곡선 함수 그래프는 다음과 같습니다. < P > 구체적으로, 내가 알고 있지만 노출되지 않은 정보를 다른 사람에게 증명하는 것입니다. (일부 지식 증명과 유사) < P > 증명서: 앞서 소개한 결합법: 해시 함수를 추가하면 간단한 수정으로 얻을 수 있습니다. 그러면 다음과 같이 알 수 있습니다. 이 시점에서 방정식은 다음과 같습니다. 단순함을 위해서, 우리는 합을 기억합니다. 이 시점에서 방정식은 다음과 같이 단순화됩니다. 위의 방정식은 무엇을 의미합니까? < P > 는 알려진 경우 위의 방정식을 제공하고 만족시킬 수 있다면 한 사람이 소유하고 있다는 것을 증명할 수 있다고 가정할 수 있습니다. 이 가설은 전제가 있는데, 만약 한 사람이 X 를 모른다면, 그는 위의 방정식을 제공하고 만족시킬 수 없다. < P > 이 전제조건을 상세히 검토한다. 만약 한 사람이 X 를 모르고 또 화해를 계산하려고 한다면 해낼 수 있을까? 결론은 안 된다는 것이다. 우선 우리는 (한정된 시간 내에) 에서 계산할 수 없다.

또 다른 질문이 있습니다. 및 를 알고 있는 경우 에 대한 정보를 계산할 수 있습니까?

공식에 따르면: 풀기만 하면 됩니다. < P > X 를 계산하려면 R 을 알아야 하는데 R 이 공개되지 않은 상태에서 R 을 계산할 수 있는 방법이 있나요? 우리는 r = r * p; 하지만 이 공식에 따르면 R (방금 소개한 수학 문제) 을 거꾸로 내놓을 수 없기 때문에 X 도 안전하다.

여기서 알고리즘의 두 번째 장점을 증명할 수 있습니다.