그리드 공격에 대해 무엇을 알고 있습니까?
먼저 타원 곡선 디지털 서명 알고리즘은 (ECDSA) 많은 코드 리뷰에서 볼 수 있는 일반적인 디지털 서명 체계입니다. 몇 가지 바람직한 속성이 있지만 비밀 난스의 1비트 미만을 드러내는 부채널 공격으로 개인 키를 복구하기에는 매우 취약할 수도 있습니다.
ECDSA디지털 서명 알고리즘의 특별한 형식입니다(DSA).DSA키 생성, 서명 및 확인의 세 가지 알고리즘으로 정의되는 상당히 일반적인 디지털 서명 체계입니다. 키 생성 알고리즘은 개인 및 공개 키를 생성합니다. 개인 키는 서명 생성을 담당합니다. 공개 키는 서명 확인을 담당합니다. 서명 알고리즘은 메시지와 개인 키를 입력으로 받아 서명을 생성합니다. 확인 알고리즘은 메시지, 서명 및 공개 키를 입력으로 사용하고 서명이 유효한지 여부를 나타내는true또는 의 값을 반환합니다 .false
DSA 는 모든 수학적 그룹에 대해 정의되며 이 체계는 이산 로그 문제가 해당 그룹에 대해 어려운 한 안전합니다. 일반적으로 사용되는 그룹은 정수 모듈로 a 소수 p입니다.
이 그룹과 함께 우리는 그룹 생성기 g와 일부 암호화 보안 해시 함수를 갖게 됩니다 H. 우리는 그것을 가정할 수 p , g 있고 H 상식이 될 것입니다.
x 키 생성은 먼저 모듈로 정수에서 값을 무작위로 선택하여 작동합니다 p . 그런 다음 값이 계산됩니다. y = g^x mod p
서명의 개인 키는 이고
x공개 키는 입니다y. 서명 키는 서명을 만들 수 있는 키이므로 비밀로 유지해야 합니다.
서명 알고리즘은 메시지 m 와 비밀 키 x에서 서명을 생성합니다. 먼저 임의의 그룹 요소가 생성됩니다 k . 이것은 논스(nonce)로 알려져 있으며 공격에 있어 중요합니다.
그런 다음 값이 계산 r = g^k mod p 되고 s = ( k^-1 ( H ( m ) + xr )) mod p
여기서 k^- 1 는 역군이고 H ( m ) 해시 m을 계산한 결과를 정수 모듈로 p로 해석한 결과이다.
서명은 한 쌍으로 정의됩니다 ( r , s ). (참고: r 또는 값 중 하나가 s와 같으면 0알고리즘이 새 값 으로 다시 시작됩니다 k .)
( r , s )검증 알고리즘은 서명 , 메시지 및 공개 키 y를 입력으로 받습니다 m . Let ŝ = s^-1 , 알고리즘은 true 를 반환하는 경우에만 r , s ≠ 0 и r = ( g H ( m ) y r ) ŝ .
이 유효성 검사는 때문에 작동 g^H( m ) y^r = g^H(m)+ xr = g^ks하므로 (g^H(m)y^r)^ŝ = g^k = r
디지털 서명 체계는 위조할 수 없는 경우 안전한 것으로 간주됩니다.
불변성은 공식적인 암호화 의미를 갖지만 높은 수준에서 비밀 키를 모르면 서명을 만들 수 없음을 의미합니다(비밀 키에서 생성된 기존 서명을 복사하지 않는 한). DSA불연속 로그의 가정 하에서 위조가 불가능한 것으로 입증되었습니다 .
디지털 서명은 수학적 그룹에 대해 정의됩니다. DSA 이 수학적 그룹으로 타원 곡선 그룹과 함께 사용하면 이라고 합니다 ECDSA. 타원 곡선 그룹은 의 쌍인 타원 곡선 점으로 구성되며 일부 에 대한 ( x , y )방정식을 만족합니다 . 이 블로그 게시물에서 알아야 할 것은 타원 곡선을 사용하여 유한 그룹을 정의할 수 있다는 것입니다. 즉, 그룹 생성기(타원 곡선 점)와 덧셈 및 점 곱셈 연산을 정확히 이와 동일하게 얻을 수 있음을 의미합니다. 정수로 할 수 있습니다. 그들은 유한한 그룹, 생성기,y^2 = x^3 + ax + ba , bg g , 유한 순서를 가질 것입니다 p. 이 블로그 게시물에서는 이러한 타원 곡선 작업 이 어떻게 작동하는지 설명하거나 알 필요가 없습니다 .
비밀 키는 x 여전히 임의의 값 modulo integers 입니다 p . ECDSA 와 동일 DSA하지만 다른 그룹에서 작동합니다. 이제 공개 키는 g가 이제 타원 곡선의 한 점이라는 점을 제외하면 y 여전히 로 계산됩니다 . y = g^x이는 y가 타원 곡선의 한 점이 될 수도 있음을 의미합니다(이전에는 y가 모듈로 p의 정수였습니다). 또 다른 차이점은 r 값을 계산하는 방법입니다. 우리는 여전히 이전과 같이 정수 모듈로 p로 임의의 nonce k를 생성합니다. 우리는 계산할 것입니다 g^k , 그러나 다시 g 타원 곡선의 한 점이므로 g^k 역시 마찬가지입니다. 따라서 계산 ( x^k , y^k ) = g^k 하고 설정할 수 있습니다 r = x^k . 이제 그 의미 s 이전과 같이 계산할 수 있으며 이전과 같이 ( r , s )여전히 모듈로 정수인 서명을 얻습니다 p . r 확인하려면 조금 다르게 계산한 사실을 수정해야 합니다 .
따라서 이전과 마찬가지로 의 값을 계산
( g^H(m)y^r)^ŝ하지만 이제 그 값은 타원 곡선의 한 점이므로x해당 점의 -좌표를 가져와 의 값과 비교합니다r.
재사용된 nonce에서 비밀 키 복구 NONCES
이제 그것이 무엇인지, 어떻게 작동하는지 이해했으므로 취약성을ECDSA 시연해 보겠습니다 . 다시 말하지만 이것은 디지털 서명 방식이므로 비밀 키는 메시지에 서명한 사람 외에는 누구에게도 공개되지 않아야 합니다.
그러나 서명자가 서명을 발행하고 사용된 nonce도 발행하면 공격자는 즉시 비밀 키를 복구할 수 있습니다 .
( r , s ) 메시지에 대한 서명을 해제 m 하고 실수로 nonce 를 사용했음을 발견했다고 가정해 보겠습니다 k .
s = ( k^-1 ( H ( m ) + xr )), 비밀 키를 쉽게 계산할 수 있기 때문에 :
s = (k^-1(H(m) + xr))
ks = H(m) + xr
ks – H(m) = xr
x = r^-1(ks – H(m))
따라서 서명자는 자신의 개인 키를 비밀로 유지해야 할 뿐만 아니라 자신이 생성한 모든 nonce도 비밀입니다.
서명자가 각 nonce를 비밀로 유지하더라도 실수로 하나의 nonce를
NONCES반복하면 (다른 메시지에 대해서도) 비밀 키를 즉시 복구 할 수도 있습니다 .NONCES
메시지에 대해 그리고 (각각) 동일한 nonce에서 생성된 두 개의 서명을 허용합니다 ( r , s 1 ) . 동일한 nonce 를 가지므로 r 값이 동일하므로 공격자가 탐지하기 매우 쉽습니다.( r , s 2 )m 1m 2k
s1 = k^-1(H(m1) + xr) and s2 = k^-1(H(m2) + xr)
s1 – s2 = k^-1(H(m1) – H(m2))
k(s1 – s2) = H(m1) – H(m2)
k = (s1 – s2)^-1(H(m1) – H(m2))
위의 공식을 사용하여 nonce를 복구하면 k 앞에서 설명한 공격을 수행하여 개인 키를 복구할 수 있습니다.
잠시 이것을 소화해 봅시다.
서명 nonce가
NONCES공개되면 비밀 키를 즉시 복구 할 수 있으므로 전체 서명 체계가 손상 됩니다 .
또한 두 개의 nonce가 반복되면 메시지가 무엇이든 공격자가 이를 쉽게 감지하고 즉시 비밀 키를 복구하여 전체 체계를 깨뜨릴 수 있습니다.
그것은 꽤 연약하고 단지 가벼운 공격 입니다 !
그러나 매우 자세하게 설명된 새로운 Lattice At tack 이 있습니다 (Joachim Breitner 및 Nadia Heninger).Йоахим Брайтнер и Надя Хенингер
문서 [PDF] : Biased Nonce Sense: 암호화폐의 취약한 ECDSA 서명에 대한 격자 공격
비트코인 블록체인에서 특정 거래를 발견했습니다.
거래: 08d917f0fee48b0d765006fa52d62dd3d704563200f2817046973e3bf6d11f1f
비트코인 주소: 15N1KY5ohztgCXtEe13BbGRk85x2FPgW8E
가짜 서명을 곱하고 그리드를 적용했습니다.
GOOGLE COLAB 에서 패키지 설치와 함께 Python 스크립트 algorithmLLL.py를 사용하는 경우
설치 >> SAGE + ECDSA + BITCOIN + 알고리즘 LLL
Private Key우리 는 .Bitcoin Wallet_ECDSA
bitaddress를 열고 다음을 확인합니다.
개인 키를 찾았습니다!
ADDR: 15N1KY5ohztgCXtEe13BbGRk85x2FPgW8E
WIF: 5JCAmNLXeSwi2SCgNH7wRL5qSQhPa7sZvj8eDwxisY5hJm8Uh92
HEX: 31AFD65CAD430D276E3360B1C762808D1D051154724B6FC15ED978FA9D06B1C1 이 비디오 는 BITCOIN 암호화폐의 취약한 ECDSA 서명에 대한 데이터 및 secp256k1 타원 곡선 암호화의 재정적 보안을 보장하기 위해 CRYPTO DEEP TECH 포털용 으로 제작되었습니다.
https://youtu.be/YP4Xj6gUcf4 – 동영상 자료
cryptodeeptech@gmail.com – 모든 질문에 대한 이메일
https://t.me/cryptodeep_tech – Telegram을 통한 기술 지원