비탈릭 부테린을 통해 비탈릭 부테린 블로그
이것은 다음 게시물의 거울입니다. https://medium.com/@VitalikButerin/탐색-타원-곡선-쌍-c73c1864e627
트리거 경고: 수학.
결정론적 임계값 서명, zk-SNARK 및 기타 간단한 형태의 영지식 증명을 포함하여 다양한 구성 뒤에 있는 주요 암호화 기본 요소 중 하나는 타원 곡선 쌍입니다. 타원 곡선 쌍(또는 "쌍선형 맵")은 암호화 및 디지털 서명을 포함한 암호화 응용 프로그램에 타원 곡선을 사용해 온 30년 역사에 최근 추가된 것입니다. 페어링은 "암호화된 곱셈" 형태를 도입하여 타원 곡선 기반 프로토콜이 수행할 수 있는 작업을 크게 확장합니다. 이 기사의 목적은 타원 곡선 쌍을 자세히 살펴보고 작동 방식에 대한 일반적인 개요를 설명하는 것입니다.
이 책을 처음 읽을 때, 심지어 열 번째 읽을 때에도 여기에 있는 내용을 모두 이해할 수는 없습니다. 이 일은 정말 어렵습니다. 하지만 이 기사가 내부적으로 무슨 일이 일어나고 있는지에 대해 최소한 약간의 아이디어를 제공할 수 있기를 바랍니다.
타원 곡선 자체는 이해하기 매우 어려운 주제이며, 이 기사에서는 일반적으로 여러분이 타원 곡선의 작동 방식을 알고 있다고 가정합니다. 그렇지 않은 경우 이 기사를 입문서로 추천합니다. https://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/. 간단히 요약하자면, 타원 곡선 암호화에는 "점"(�,�) 좌표가 있는 문자 그대로의 2차원 점)이라는 수학적 개체와 이를 더하고 빼기 위한 특수 공식(예: �=의 좌표 계산)이 포함됩니다. �+�), 그리고 점에 정수를 곱할 수도 있습니다(예: �⋅�=�+�+…+�, �가 큰 경우 계산하는 훨씬 빠른 방법이 있습니다).
점 산술에서 0에 해당하는 "무한점"(�)이라는 특별한 점이 있습니다. 항상 �+�=�인 경우입니다. 또한 곡선에는 "주문“; 임의의 �에 대해 �⋅�=�과 같은 숫자 �가 존재합니다(물론 �⋅(�+1)=�,�⋅(7⋅�+5)=�⋅5 등). 또한 어떤 의미에서 숫자 1을 나타내는 것으로 이해되는 "생성기 점"에 대해 일반적으로 동의하는 몇 가지가 있습니다. 이론적으로 곡선 위의 모든 점(... 제외)은 .일 수 있습니다. 중요한 것은 �이 표준화되어 있다는 것입니다.
페어링은 타원 곡선 점에서 특정 종류의 더 복잡한 방정식을 확인할 수 있다는 점에서 한 단계 더 나아갑니다. 예를 들어 �=�⋅�,�=�⋅� 및 �=�⋅�인 경우 다음을 확인할 수 있습니다. �⋅�=�이 아니라 �,� 및 �만 입력으로 사용합니다. 이는 P에 대한 정보가 P를 아는 것만으로도 누출되기 때문에 타원 곡선의 근본적인 보안 보장이 깨지는 것처럼 보일 수 있지만 누출이 매우 포함되어 있음이 밝혀졌습니다. 결정적인 Diffie Hellman 문제 쉽지만 계산적인 Diffie Hellman 문제(위 예에서 � 및 �를 알면 컴퓨팅 �=�⋅�⋅�) 및 이산 로그 문제 (�에서 �를 복구하는 것)은 계산적으로 실행 불가능한 상태로 유지됩니다(적어도 이전에 있었다면).
페어링이 수행하는 작업을 살펴보는 세 번째 방법이자 우리가 다루고 있는 대부분의 사용 사례에 대해 가장 잘 설명하는 방법은 타원 곡선 점을 단방향 암호화된 숫자(즉, ����)로 보는 것입니다. ���(�)=�⋅�=�), 전통적인 타원 곡선 수학을 사용하면 다음을 확인할 수 있습니다. 선의 숫자에 대한 제약 조건(예: �=�⋅�,�=�⋅� 및 �=�⋅�인 경우 5⋅�+7⋅�=11⋅�을 확인하는 것은 정말 5⋅�+7⋅�=11⋅�)을 확인하면 페어링을 통해 확인할 수 있습니다. XNUMX 차 제약 조건(예: �(�,�)⋅�(�,�⋅5)=1 확인은 정말 �⋅�+5=0인지 확인). 그리고 XNUMX차 연산으로 올라가는 것만으로도 결정론적 임계값 서명, XNUMX차 산술 프로그램 및 기타 모든 좋은 작업을 수행할 수 있습니다.
자, 위에서 소개한 재미있는 �(�,�) 연산자는 무엇일까요? 이것이 페어링입니다. 수학자들은 때때로 그것을 다음과 같이 부릅니다. 이중선형 지도; 여기서 "bilinear"라는 단어는 기본적으로 제약 조건을 충족한다는 의미입니다.
�(�,�+�)=�(�,�)⋅�(�,�)
�(�+�,�)=�(�,�)⋅�(�,�)
+ 및 ⋅는 임의의 연산자일 수 있습니다. 멋지고 새로운 종류의 수학적 객체를 만들 때 추상 대수학은 +와 ⋅가 어떻게 되는지는 신경 쓰지 않습니다. 한정된, 예를 들어 일반적인 방식으로 일관성을 유지하는 한. �+�=�+�,(�⋅�)⋅�=�⋅(�⋅�) 및 (�⋅�)+(�⋅�)=(�+�)⋅�.
�, �, � 및 �가 단순한 경우 숫자, 그러면 간단한 페어링을 만드는 것이 쉽습니다. �(�,�)=2��를 수행할 수 있습니다. 그러면 다음을 볼 수 있습니다.
�(3,4+5)=23⋅9=227
�(3,4)⋅�(3,5)=23⋅4⋅23⋅5=212⋅215=227
이중 선형입니다!
그러나 이러한 간단한 쌍은 작업하는 개체가 단순한 정수이고 분석하기가 너무 쉽기 때문에 암호화에 적합하지 않습니다. 정수를 사용하면 나누기, 로그 계산 및 기타 다양한 계산이 쉬워집니다. 단순 정수에는 "공개 키" 또는 "단방향 함수" 개념이 없습니다. 또한 위에서 설명한 페어링을 사용하면 �를 알고 �(�,�)를 알면 간단히 나눗셈과 로그를 계산하여 �을 결정할 수 있습니다. 우리는 더하기, 빼기, 곱하기, 나누기를 할 수 있는 "블랙박스"에 최대한 가까운 수학적 객체를 원합니다. 하지만 다른 건 아무것도 하지 않아. 여기서 타원 곡선과 타원 곡선 쌍이 사용됩니다.
타원 곡선 점에 대해 이중선형 맵을 만드는 것이 가능하다는 것이 밝혀졌습니다. 즉, 입력 � 및 �가 타원 곡선 점이고 출력이 호출되는 함수 �(�,�)를 생각해 내는 것이 가능하다는 것이 밝혀졌습니다. (��)12 요소(적어도 여기서는 구체적인 경우를 다룰 것입니다. 세부 사항은 곡선의 세부 사항에 따라 다르며 이에 대해서는 나중에 자세히 설명합니다.) 그러나 그 뒤에 있는 수학은 매우 복잡합니다.
먼저 프라임 필드와 확장 필드를 살펴보겠습니다. 이 게시물의 앞부분에 있는 그림의 예쁜 타원 곡선은 곡선 방정식이 일반 실수를 사용하여 정의된다고 가정하는 경우에만 그렇게 보입니다. 그러나 실제로 암호화에 일반 실수를 사용하는 경우 로그를 사용하여 "뒤로 이동"할 수 있으며 모든 것이 중단됩니다. 또한 실제로 숫자를 저장하고 표현하는 데 필요한 공간이 임의로 늘어날 수 있습니다. 따라서 우리는 대신에 숫자를 사용합니다. 프라임 필드.
소수 필드는 0,1,2…
�+�:(�+�) % �
�⋅�:(�⋅�) % �
�−�:(�−�) % �
�/�:(�⋅��−2) % �
기본적으로 모든 수학은 모듈로 수행됩니다. 여기에서 지금 확인해 보세요. 모듈러 수학에 대한 소개). 나눗셈은 특별한 경우입니다. 일반적으로 32는 정수가 아니며 여기서는 정수만 다루고 싶기 때문에 대신 ⋅2=3이 되는 숫자 �를 찾으려고 합니다. 여기서 ⋅는 물론 위에 정의된 모듈러 곱셈을 나타냅니다. 덕분에 페르마의 작은 정리, 위에 표시된 지수 트릭이 작업을 수행하지만 다음을 사용하여 이를 수행하는 더 빠른 방법도 있습니다. 확장된 유클리드 알고리즘. �=7; 다음은 몇 가지 예입니다.
2+3=5 % 7=5
4+6=10 % 7=3
2−5=−3 % 7=4
6⋅3=18 % 7=4
3/2=(3⋅25) % 7=5
5⋅2=10 % 7=3
이런 종류의 수학을 시험해 보면 그것이 완벽하게 일관되고 일반적인 규칙을 모두 충족한다는 것을 알 수 있습니다. 위의 마지막 두 예는 (�/�)⋅�=�; 방법을 보여줍니다. 또한 (�+�)+�=�+(�+�),(�+�)⋅�=�⋅�+�⋅� 및 여러분이 알고 사랑하는 다른 모든 고등학교 대수학 정체성이 계속되는 것을 볼 수 있습니다. 사실을 유지하는 것도 마찬가지입니다. 실제로 타원 곡선에서 점과 방정식은 일반적으로 소수 필드에서 계산됩니다.
이제 이야기 해 봅시다 확장 필드. 이전에 이미 확장 필드를 본 적이 있을 것입니다. 수학 교과서에서 접할 수 있는 가장 일반적인 예는 실수 필드가 추가 요소 −1=�로 "확장"되는 복소수 필드입니다. 기본적으로 확장 필드는 기존 필드를 가져온 다음 새 요소를 "발명"하고 해당 요소와 기존 요소 간의 관계(이 경우 �2+1=0)를 정의하여 이 방정식이 참이 되지 않도록 하는 방식으로 작동합니다. 원래 필드에 있는 모든 숫자에 대해 원래 필드 요소와 방금 생성한 새 요소의 모든 선형 조합 집합을 살펴봅니다.
(2+3�)+(4+2�)=6+5�
(5+2�)+3=1+2�
(6+2�)⋅2=5+4�
4�⋅(2+�)=3+�
마지막 결과는 파악하기가 약간 어려울 수 있습니다. 거기서 일어난 일은 먼저 곱을 4�⋅2+4�⋅�로 분해하여 8�−4를 제공한 다음 mod7 수학에서 작업하고 있기 때문에 �+3이 된다는 것입니다. 나누려면 다음을 수행합니다.
�/�:(�⋅�(�2−2)) % �
페르마의 작은 정리의 지수는 이제 � 대신 �2입니다. 하지만 다시 한 번 더 효율적으로 작업을 수행하려면 확장 유클리드 알고리즘을 확장할 수도 있습니다. 이 필드의 모든 �에 대해 ��2−1=1이므로 �2−1을 "필드의 곱셈 그룹의 순서"라고 부릅니다.
실수의 경우, 대수학의 기본정리 우리가 복소수라고 부르는 이차 확장이 "완전"하다는 것을 보장합니다. 더 이상 확장할 수 없습니다. 왜냐하면 어떤 수학적 관계(적어도 대수 공식으로 정의된 모든 수학적 관계) 때문에 새로운 요소 사이에서 찾아낼 수 있기 때문입니다. � 그리고 기존 복소수를 사용하면 이미 해당 관계를 만족하는 복소수를 하나 이상 생각해내는 것이 가능합니다. 그러나 소수 필드를 사용하면 이 문제가 없으므로 더 나아가 1차 확장을 만들 수 있습니다(여기서 일부 새 요소 �와 기존 필드 요소 사이의 수학적 관계는 2차 방정식이므로 XNUMX,� 및 �XNUMX는 다음과 같습니다). 모두 서로 선형 독립), 고차 확장, 확장의 확장 등. 그리고 타원 곡선 쌍이 구축되는 것은 이러한 종류의 과급 모듈러 복소수입니다.
이러한 모든 작업을 코드로 작성하는 데 관련된 정확한 수학을 보고 싶은 사람들을 위해 프라임 필드와 필드 확장이 여기에 구현되어 있습니다. https://github.com/ethereum/py_pairing/blob/master/py_ecc/bn128/bn128_field_elements.py
이제 타원 곡선 쌍을 살펴보겠습니다. 타원 곡선 쌍(또는 여기에서 살펴볼 특정 형태의 쌍; 논리는 상당히 유사하지만 다른 유형의 쌍도 있음)은 맵 �2×�1→��입니다. 여기서:
- �1은 점이 �2=�3+� 형식의 방정식을 충족하고 두 좌표가 모두 ��의 요소인 타원 곡선입니다.
- �2는 좌표가 (��)1의 요소인 경우를 제외하고 점이 �12과 동일한 방정식을 만족하는 타원 곡선입니다(즉, 위에서 설명한 과급 복소수입니다. 새로운 "마법수"를 정의합니다. ” �, �12−12⋅�18+6=82과 같은 0차 다항식으로 정의됨)
- ��는 타원 곡선의 결과가 들어가는 객체의 유형입니다. 우리가 보는 곡선에서 ��는 (��)12(�2에서 사용된 것과 동일한 과급 복소수)입니다.
충족해야 하는 주요 속성은 이중선형성입니다. 이 맥락에서 이는 다음을 의미합니다.
- �(�,�+�)=�(�,�)⋅�(�,�)
- �(�+�,�)=�(�,�)⋅�(�,�)
다른 두 가지 중요한 기준이 있습니다.
- 효율적인 계산 가능성 (예: 단순히 모든 점의 이산 로그를 취하여 함께 곱함으로써 쉽게 페어링할 수 있지만, 이는 애초에 타원 곡선 암호화를 깨뜨리는 것만큼 계산적으로 어렵기 때문에 계산되지 않습니다.)
- 비퇴행성 (물론 �(�,�)=1로 정의할 수도 있지만 특별히 유용한 페어링은 아닙니다.)
그럼 우리가 어떻게해야합니까?
페어링 기능이 작동하는 이유에 대한 수학은 매우 까다롭고 지금까지 본 것보다 훨씬 더 많은 고급 대수학을 포함하지만 개요를 제공하겠습니다. 우선, 우리는 a의 개념을 정의해야 합니다. 분할기, 기본적으로 타원 곡선 점에서 함수를 나타내는 대체 방법입니다. 함수의 제수는 기본적으로 함수의 0과 무한대를 계산합니다. 이것이 무엇을 의미하는지 알아보기 위해 몇 가지 예를 살펴보겠습니다. 어떤 점 �=(��,��)을 수정하고 다음 함수를 고려해 보겠습니다.
�(�,�)=�−��
제수는 [�]+[−�]−2⋅[�]입니다(대괄호는 우리가 언급하고 있는 사실을 나타내는 데 사용됩니다). 함수의 0과 무한대 집합에 점 �의 존재, 포인트 P 자체가 아닙니다. [�]+[�]는 지원 [�+�]와 동일합니다. 추론은 다음과 같습니다.
- 함수는 �에서 0과 같습니다. 왜냐하면 �이기 때문입니다. is ��, 따라서 �−��=0
- −�와 �가 동일한 � 좌표를 공유하므로 함수는 −�에서 0과 같습니다.
- �이 무한대로 가듯이 함수도 무한대로 갑니다. 그래서 우리는 함수가 �에서 무한대와 같다고 말합니다. 이 무한대가 두 번 계산되어야 하는 기술적인 이유가 있으므로 �은 "다중수" -2로 추가됩니다(무한대이기 때문에 음수이고 XNUMX이 아니기 때문에 음수이고 이중 계산으로 인해 XNUMX입니다).
기술적인 이유는 대략 다음과 같습니다: 곡선 방정식이 �3=�2+�이기 때문에� �1.5가 �2을 따라잡기 위해 �보다 “3배 더 빠르게” 무한대로 이동합니다. 따라서 선형 함수에 �만 포함되면 다중도 2의 무한대로 표시되고, �를 포함하면 다중도 3의 무한대로 표시됩니다.
이제 "라인 함수"를 고려해보세요.
��+��+�=0
여기서 �, � 및 �는 선이 � 및 � 점을 통과하도록 신중하게 선택됩니다. 타원 곡선 추가가 작동하는 방식으로 인해(상단 다이어그램 참조) 이는 −�−�를 통과한다는 의미이기도 합니다. 그리고 �과 � 모두에 따라 무한대로 올라가므로 제수는 [�]+[�]+[−�−�]−3⋅[�]가 됩니다.
두 함수 � 및 �에 대해 �⋅�의 제수는 �의 제수에 �의 제수를 더한 것과 같습니다(수학 교과서에서는 (�⋅�)=(�)+(�)로 표시됨). 예를 들어 �(�,�)=��−�이면 (�3)=3⋅[�]+3⋅[−�]−6⋅[�]; � 및 −�는 특정 수학적 의미에서 "3배 빠르게" 해당 지점에서 �0이 XNUMX에 접근한다는 사실을 설명하기 위해 "XNUMX중 계산"됩니다.
함수의 제수에서 "대괄호를 제거"하면 점의 합은 �([�]+[�]+[−�−�]−3⋅[가 되어야 한다는 정리가 있습니다. �]는 �+�−�−�−3⋅�=�와 같이 명확하게 적합하며 이 속성을 갖는 모든 제수는 함수의 제수입니다.
이제 Tate 페어링을 살펴볼 준비가 되었습니다. 제수를 통해 정의된 다음 함수를 고려하세요.
- (��)=�⋅[�]−�⋅[�], 여기서 �는 �1의 차수입니다. �⋅�=� 모든 �에 대해
- (��)=�⋅[�]−�⋅[�]
- (�)=[�+�]−[�]−[�]+[�]
이제 제품 ��⋅��⋅��를 살펴보겠습니다. 제수는 다음과 같습니다.
�⋅[�]−�⋅[�]+�⋅[�]−�⋅[�]+�⋅[�+�]−�⋅[�]−�⋅[�]+�⋅[�]
다음과 같이 깔끔하게 단순화됩니다.
�⋅[�+�]−�⋅[�]
이 제수는 위의 �� 및 ��에 대한 제수와 정확히 동일한 형식입니다. 따라서 ��⋅��⋅��=��+�입니다.
이제 "최종 지수" 단계라는 절차를 소개합니다. 여기서는 위 함수(��,�� 등)의 결과를 �=(�12−1)/� 거듭제곱합니다. 여기서 �12−1은 (��)12의 곱셈 그룹의 차수입니다(즉, 어떤 �∈(��)12,�(�12−1)=1). 다음과 같은 결과에 이 지수화를 적용하면 이미 �의 거듭제곱으로 올리면 �12−1의 거듭제곱을 얻게 되므로 결과는 1이 됩니다. 따라서 최종 지수화 후에 ��는 상쇄되고 ����⋅���=(를 얻습니다. ��+�). 당신에게는 약간의 이중성이 있습니다.
이제 두 인수 모두에서 이중선형인 함수를 만들려면 더 으스스한 수학으로 들어가야 합니다. 여기서는 값의 ��를 직접 취하는 대신 값의 ��를 취해야 합니다. 분할기, 그리고 그것이 완전한 "Tate pairing"이 나오는 곳입니다. 더 많은 결과를 증명하려면 "선형 등가" 및 "Weil 상호성"과 같은 개념을 다루어야 하며 거기서부터 토끼굴이 계속됩니다. 이 모든 것에 대한 더 많은 독서 자료를 찾을 수 있습니다 여기에서 지금 확인해 보세요. 과 여기에서 지금 확인해 보세요..
최적의 Ate 페어링이라고 불리는 수정된 버전의 Tate 페어링을 구현하기 위해, 여기를 참조. 코드는 다음을 구현합니다. 밀러의 알고리즘, 실제로 ��를 계산하는 데 필요합니다.
이와 같은 페어링이 가능하다는 사실은 다소 혼합된 축복입니다. 한편으로는 페어링으로 수행할 수 있는 모든 프로토콜이 가능해짐을 의미하지만 타원 곡선에 대해 더 주의해야 한다는 의미이기도 합니다. 우리는 사용.
모든 타원 곡선에는 다음과 같은 값이 있습니다. 매립 정도; 본질적으로 ��−1이 �의 배수인 가장 작은 �입니다(여기서 �는 필드에 사용되는 소수이고 �는 곡선 순서입니다). 위의 필드인 �=12와 전통적인 ECC에 사용되는 필드(즉, 쌍을 고려하지 않는 곳)에서는 쌍을 계산하는 것이 계산적으로 불가능할 정도로 임베딩 정도가 종종 매우 큽니다. 그러나 조심하지 않으면 �=4 또는 심지어 1인 필드를 생성할 수 있습니다.
�=1이면 타원 곡선에 대한 "이산 로그" 문제(본질적으로 �=�⋅� 점만 알고 � 복구, 타원 곡선 개인 키를 "크래킹"하기 위해 해결해야 하는 문제)가 줄어들 수 있습니다. ��에 대해 비슷한 수학 문제를 풀면 문제가 훨씬 쉬워집니다(이를 MOV 공격); 임베딩 수준이 12 이상인 곡선을 사용하면 이러한 감소를 사용할 수 없거나 페어링 결과에 대한 이산 로그 문제를 해결하는 것이 적어도 "일반적인 방법"으로 공개 키에서 개인 키를 복구하는 것만큼 어렵습니다(예: 계산적으로 불가능함). 걱정 하지마; 이 문제에 대해 모든 표준 곡선 매개변수를 철저히 확인했습니다.
곧 제공될 zk-SNARK 작동 방식에 대한 수학적 설명을 계속 지켜봐 주시기 바랍니다.
검토하고 수정해준 Christian Reitwiessner, Ariel Gabizon(Zcash 출신) 및 Alfred Menezes에게 특별히 감사드립니다.
- SEO 기반 콘텐츠 및 PR 배포. 오늘 증폭하십시오.
- PlatoData.Network 수직 생성 Ai. 자신에게 권한을 부여하십시오. 여기에서 액세스하십시오.
- PlatoAiStream. 웹3 인텔리전스. 지식 증폭. 여기에서 액세스하십시오.
- 플라톤ESG. 탄소, 클린테크, 에너지, 환경, 태양광, 폐기물 관리. 여기에서 액세스하십시오.
- PlatoHealth. 생명 공학 및 임상 시험 인텔리전스. 여기에서 액세스하십시오.
- BlockOffsets. 환경 오프셋 소유권 현대화. 여기에서 액세스하십시오.
- 출처: 플라톤 데이터 인텔리전스.
