
[암호학] 공개 키 기반의 대칭 키 교환

트랜잭션 T는 다음 data를 포함한다.
T = { nonce, gasPrice, gasLimit, to, value, data, v, r, s }
function selector
와 그 이후의 function argument
를 serialize한 data이다.function selector = (keccak-256(function prototype))[0:4]
서명 시 사용되는 트랜잭션 T는 9개 필드로 다음과 같다. 이 중 맨 끝의 3개 { chainID, 0, 0 }은 EIP-155에 의해 추가된다. EIP-155는 Simple Replay Attack Protection으로 chainID를 포함하여 다른 네트워크 체인에서 해당 트랜잭션이 replay될 수 없도록 한다.
T = { nonce, gasPrice, gasLimit, to, value, data, chainID, 0, 0 }
Sig는 서명으로 서명 알고리즘, F sig() 로 (r, s) 두 값이 output으로 만들어진다. Transaction T와 private key k를 사용한다. RLP는 Recursive Length Prefix (RLP) encoding scheme 을 말한다.
Sig = F sig(keccak256(RLP(T)), k) = (r, s)
서명 시에는 임시 private key q, 그리고 q로부터 생성되는 임시 public key Q 를 사용한다.
q = rand() % 2**256
Q = q * K = (x, y)
여기서 r = Q의 x 좌표이다. s는 다음으로 계산된다.
s ≡ q**-1 (Keccak-256(RLP(T)) + r * k) mod p
r, s 그리고 sender의 public key K를 사용해서 Q를 계산한다. Q의 x 좌표와 r이 같으면 서명이 유효하다.
w = s-1 mod p
u1 = Keccak-256(RLP(T)) * w mod p
u2 = r * w mod p
Q ≡ u1 * G + u2 * K (mod p)
참고: https://github.com/ethereumbook/ethereumbook/blob/develop/06transactions.asciidoc
https://github.com/ethereumbook/ethereumbook 에서 최신판을 볼 수 있다.
현재 판매되는 서적은 이전 내용을 담고 있다.
String match algorithm인 KMP algorithm은 text에서 뛰어넘을 수 있는 만큼 뛰어넘으면서 string이 match되는지 확인한다. 여기서 얼마나 뛰어넘을 수 있는지에 대한 정보를 얻기 위해 Failure function이라는 함수를 이용한다.
Failure function은 찾으려는 string의 각 위치마다 공통인 prefix와 suffix의 최대 길이를 찾아 저장해둔다. 예를 들면, “ababa” 는 { 0, 0, 1, 2, 3 } 과 같이 저장한다. 구현 시에는 -1 해서 저장한다. 예에서의 값은 { -1, -1, 0, 1, 2 } 이 된다.
void get_failure_function(char str[], int len, int failure[]) { int i; failure[0] = -1; for (i = 1; i < len; i++) { int f = failure[i - 1]; while (1) { if (str[i] == str[f + 1]) { failure[i] = f + 1; break; } if (f <= -1) { failure[i] = -1; break; } f = failure[f]; } } }
찾을 때는, 위에서 계산한 값을 이용해 string을 찾는 도중에 틀리면 바로 이전까지 맞았던 부분의 failure function value를 찾아 이전까지 같은 부분을 건너뛰고 다음 부분부터 비교한다. 예를 들어, 위의 string을 찾으려고 할 때, text가 “ababcababa” 라면, string의 처음부터 비교하다가 5번째에서 틀리면, 4번째까지는 맞으므로, 4번째의 failure function value를 찾으면 2이다. 이는 앞의 2글자는 맞다는 말이므로, text에서 4-2 만큼을 건너뛴 후, string의 3번째부터 다시 비교한다. string의 3번째도 틀리므로, 2번째의 failure function value를 찾으면 0인데, 이는 0만큼 맞다는 말(=하나도 안맞다는 말)이므로 text를 2-0 만큼 건너뛴 후, string의 1번째와 다시 비교한다. string의 첫번째와 다르면 1만큼만 이동하고, 다시 1번째와 비교한다. 맞았을 때도 맞은 부분만큼을 이용해서 건너뛴다(5번째에서 맞았으므로, 3글자가 맞고, 5-3만큼 이동한 후, 4번째부터 비교).
아래 구현은 match되는 개수를 return하도록 하였다.
int get_matched_count(char text[], int text_len, char string[], int str_len, int failure[]) { int count = 0; int t = 0; int s = 0; while (t < text_len - str_len + 1) { while (s < str_len) { if (text[t + s] != string[s]) break; s++; } if (s == str_len) { // MATCH! count++; } if (s < 1) { t++; s = 0; } else { t += s - 1 - failure[s - 1]; s = failure[s - 1] + 1; } } return count; }
앞 부분과 공통 부분이 없는 string인 경우, 더 빨리 건너뛴다. 예를 들면, “abababababc” 에서 “ababc”({ 0, 0, 1, 2, 0 })를 찾는 경우, 5번째에서 틀리면, 앞에서부터 0글자가 같으므로, 4-0만큼 이동한 후, 1번째부터 다시 비교한다.
위 두 구현 함수의 사용 부분은 다음과 같이 될 것이다.
int T, S; int count; int *failure_function = NULL; char *text = "ababcababababababababa"; char *string = "ababa"; T = strlen(text); S = strlen(string); failure_function = (int *)malloc(sizeof(int) * S); // skip the check of the memory allocation get_failure_function(string, S, failure_function); count = get_matched_count(text, T, string, S, failure_function); printf("%d matched\n", count);