controlpro
[암호 SW 개발] 큰정수 지수승 본문
모듈러 지수 연산 알고리즘 : A^E mod M (ek ek-1 , ,,,,,, e1 , e0)
- Left-to-Right Exponentiation
> 지수 E의 최상위 자리(ek) 부터 모듈로 지수연사을 수행
- Right-to-Left Exponentiation
> 지수 E의 최하위 자리 부터 모듈러 지수 연사을 수행
- Left-to-Right k-ary Exponentiation
> 지수 E를 k-ary로 나누어 사전 계싼을 한 후 지수 연산을 수행
> E = (ek, ek-1 , ,,,,, e1 , e0)2 = (kt, kt-1 ,,,, k1, k0)
LtR 4-ary 지수승
- LtR의 확장판
- 사전계산 테이블을 이용하여 연산량 개선
알고리즘은 다음과 같다. 기본적으로 여기서의 곱셈은 mod연산을 생각하고 있지 않기 때문에 매 곱셈을 할 때마다 mod 연산을 해준다고 생각해도 된다.( A * B mod N) = (A mod N) * (B mod N) mod N 이므로 (일반적인 경우)
Input
보통 A ^ E 라는 것을 구할 때 e가 지수승이고 e는 여기서 32bit의 연산단위이다. k는 0일 때는 무조건 값이 1이기 때문에 k>=1의 경우의 수만 생각한다.
Precomputation
4개의 bit를 기준으로 연산이 진행되기 때문에 4개의 비트의 연산결과를 모두 저장해야한다. 즉, 2^4의 경우의 수 16개의 경우의 수를 모두 미리 연산을 해두어야 한다. 따라서 곱해지는 수가 A라고하면 내가 사전에 계산해야하는 수는 아래와 같다.
| A , A^2 , A^3 , A^4 , A^5 , A^6 ........ A^15 |
코드
for (i = 1; i < 16; i++) {
MPZ_MODMUL(&S[i], &S[i - 1], input, mod); // 각각의 사비트의 계산이 필요하다.
}여기서 S는 미리 선언해둔 MPZ 파일 형식이고 for문을 이용해서 15번씩 곱하면, 계산이 된다.(자기 자신은 굳이 계산하지 않아도 된다.)
사전 전처리 과정에서 중요한 작업은 내가 지수부의 길이이다.
다음과 같이 블럭이 있다고 가정을 해보자. 주황색 블록은 32bit변수를 담을 수 있는 word 사이즈고 파란색은 구분을 쉽게하기 위한 빈 공간이다. Block1은 호텔이라고 생각하고, 각 방은 4bit로 이루어진 스위트룸이 있고 4bit에 각각 방이 4개가 있다고 가정하면 편하다.
코드 상에서는 wlen이 4bit로 이루어진 스위트룸 explen이 방의 개수이다.
한마디로 E 값을 4로 나눈 값이 wlen , E값의 비트의 수가 explen이다.
(((((((1) ^ 2 ^k) * m ^5 )^2^k) * m^13)^2^k) * m^11)
이런 식으로 곱한다고 가정을 했을 때 내가 초기에 곱해야하는 값을 정하기 위해서 앞의 네자리를 가져와야 한다. (알고리즘 상에서 3.1번째를 계산하기 위해서)
네자리를 가져오기 위해서 explen을 먼저 계산한다.(전에 했던것이 있으므로)
for (i = 31; i >= 0; i--)
{
if ((exp->dat[exp->len - 1] & (1 << i)))
break;
}
explen = (exp->len - 1) * 32 + i;exp의 len에서 1이 가장 먼저 나온 곳을 찾고, 그 뒤가 길이가 되니까 나머지 블록은 모두 1로 차있다고 가정을 하면
앞의 i값에서 나머지 블록의 개수 * 32 하면 총 비트의 수가 나온다.
예를 들면
00011001 11110000 11001100 라는 수가 있다고 가정을 해보면 (여기서는 편의상 8이라고 가정하자)
이 수의 총 비트의 길이는 앞의 000을 제외한 길이가 될 것이다. 즉
11001 11110000 11001100 => (최상의 비트) + (나머지 블록의 수 * 8) 이므로
=> (5개) + (2 * 8) = 21
총 21 비트라고 할 수 있따.
그러면 일단 wlen은 어떻게 계산하는 것일까. w가 4bit의 연산단위라고 해보자. 위의 연산 단위에서 4개의 블록이 몇개 차 있는 가? 가 wlen에서 궁금한 내용이다.
wlen = (explen + 3) / 4;아까의 예를 그대로 들자면
11001 11110000 11001100를 4개의 블록 단위로 나누면
0001 1001 1111 0000 1100 1100 으로 되서 총 wlen의 길이는 6개이다.
따라서 6개의 블록이 만들어진다.
여기서 wlen은 21 // 4 = 5 인데 1개의 블록이 더 필요하니까 3을 더 더해줘서 4로 나누면 남는 비트도 계산이 된다.
초기값으로 넣어줘야하기 때문에 3.1의 A^(2^k) 값을 먼저 계산해야한다.
COPY_MPZ(&x, &S[(exp->dat[exp->len - 1] >> (4 * ((wlen + 7) % 8))) & 15]);A^(2^k)를 저장하는 부분이다. 이 부분이 많이 헷갈렸을 거 같은데,
8로 나누는이유는 4 * 8 = 32 이기 때문에 4bit 단위의 것들을 얼마나 밀어야 되는 지 나오기 때문이다.
결국 나머지에 해당하는 밀어야하는 비트를 보면
나머지 밀어야 비트 0 28 1 0 2 4 3 8 4 12 5 16 6 20 7 24
00000000 00111111 11111111 1111 이럴 경우에 최종적으로는 111111 11111111 1111 에서 상위 4bit만 필요하니까 뒤에가 딱 맞아떨어진다고 가정을 하면 0011 이렇게 때어진다고 보고 A^3을 초기 값으로 설정을 해주면 되는 것이다.
이제 알고리즘에서 2.1을 계산을 해야하는데 여기서 k값 (A)^(2^k) 에서 k==4니까, A^16 계산을 해야한다.
for (i = wlen - 2; i >= 0; i--)
{
MPZ_MODMUL(&y, &x, &x, mod); // x <== x^2
MPZ_MODMUL(&x, &y, &y, mod); // x <== x^4
MPZ_MODMUL(&y, &x, &x, mod); // x <== x^8
MPZ_MODMUL(&x, &y, &y, mod); // x <== x^16
MPZ_MODMUL(&y, &x, &S[(exp->dat[i/8]>>((i%8)*4))&15], mod);
COPY_MPZ(&x, &y);
}
마지막에는 x에 return 하기 위해서 r로 넣어주면 된다.