저번 수업 시간에 이해하기 어려웠던 SubBytes와 mixcolumn을 복습해보자.
SubBytes 계산
SubBytes 계산은 평문을 S-box에 있는 값으로 치환하기 위해서 수행한다.
계산은 주로 modular연산을 활용해서 갈로아 필드 환경이라고 가정하고 계산한다.
계산 방법
SubBytes를 하려면 먼저 역원이 있어야 한다. 95의 역원을 구해보자.
가장 먼저 95를 2진수로 나타낸다. -> 1001 0101
그 다음 이진수를 polynomial로 변환한다. -> x^7 + x^4 + x^2 + 1
이제 irreducible polynomial을 활용해서 이 다항식의 몫과 나머지를 차례로 구하며 역원을 알아낼 수 있다. 전에 배운 대로, Affine transaction에서 irreducible은 다음 다항식을 표준으로 사용한다.
GF(2^8)에서 x^8 + x^4 + x^3 + x + 1
이제부터 나눗셈을 여러 번 진행할 텐데, 이 때 중요한 값은 다음과 같다.
| q | r1 | r2 | r | t1 | t2 | t |
|---|---|---|---|---|---|---|
| 몫 | 나눠진 숫자(irreducible) | 나눈 숫자 | 나머지 | 초기값 0 | 초기값 1 | 해당 단계의 타겟값 |
t = t1 - t2 × q
그런데 modular 연산에서 뺄셈은 덧셈과 같으므로
t = t1 + t2 × q
나눗셈을 해보면 첫 번째 결과는 다음과 같다.
| q | r1 | r2 | r | t1 | t2 | t |
|---|---|---|---|---|---|---|
| x | x^8 + x^4 + x^3 + x + 1 | x^7 + x^4 + x^2 + 1 | x^5 + x^4 + 1 | 0 | 1 | x |
그리고 다음 단계로 갈 때, 이 중 r2, r, t2, t는 아래 단계의 왼쪽 1칸으로 이동한다.
r2 -> r1(new), r -> r2(new), t2 -> t1(new), t -> t2(new)
쉽게 외우려면 2가 1이 되고 0은 2가 된다고 생각하면 될듯...
그렇게 계산을 계속 하다보면 r1(나눠지는 수)이 1, r2(나누는 수)가 0이 되는 상황이 발생한다. 이러면 계산이 끝난 것인데, 이 때의 t1값이 역원이 된다.
그런데 생각해보자. r1이 1, r2가 0이라면 직전 계산에서 r2는 1이고 r이 0이었을 것이다. 그리고 t2에 있던 값이 새로운 t1이 되었다.
이를 통해, r2가 1이 되는 상황에 t2값이 곧 구하는 정답이라는 사실을 알 수 있다. 이 방법을 활용하면 계산을 끝까지 마치지 않아도 된다.
이제 구한 역원으로 SubBytes를 해보자.
S(x) = Ax^(-1) + b
여기서 x^(-1)은 역원 구하기로 알아낼 수 있다.
A 행렬은 10001111 을 여러번 shift해서 만든 그것...
이 때 x^(-1)은 순서를 뒤집어야 한다.
예를 들어 83이라면 이진수에서는 10000011이므로 11000001로 계산해야 한다.
1행이 [10001111]이고 역원이 [10000011] 이라면 각 자리에 맞는 숫자를 곱해서 전부 더한다. 이 때 modular 연산이므로 덧셈이 뺄셈과 같다.
따라서 1이 홀수개 -> 1, 짝수개 -> 0이 답이라고 생각하면 된다.
마지막으로 63(01100011)과 더하면(모듈러) 된다.
답은 항상 밑에서부터 읽기!!!
shift row
열을 왼쪽으로 0칸, 1칸, 2칸, 3칸...씩 당긴다.
MixColumn
생성한 S-box값을 기준 행렬과 열 단위로 곱하는 연산이다.
일반적으로 위 행렬 값을 활용한다.
예를 들어 바꾸려는 암호의 첫 번째 열이 [63, F2, 7D, D4] 라고 해보자.
그러면 63 * 2, F2 * 3, 7D * 1, D4 * 1 로 계산한다.
이때 1을 곱하는 것은 의미가 없으니 넘어가고,
비트 단위에서 2를 곱한다 = left shift, 3을 곱한다 = 2x + x이므로
2, 3과 곱하는 계산을 할 때는 각각 ls, ls+자기자신 더하기로 계산하면 된다.
그런데 left shift를 하다 보면 carry가 발생할 때가 있을 것이다.
예를 들어 F2는 비트로 치환하면 1111 0010 이므로 left shft시 1이 캐리로 발생하고 1110 0100이 된다.
이럴 때는 11b와 XOR 연산을 진행해서 carry를 없앤다.
11b는 2진수로 치환하면 1 0001 1011이다. 그러면 가장 왼쪽의 1은 XOR시 0으로 없어지기 때문에 carry를 줄일 수 있다.
이후 shiftleft 한 값과 자기자신을 더하는 연산을 하는데, 이 때도 덧셈이 아니라 XOR을 해야 한다. (중요)
이런 식으로 계산을 전부 다 한 뒤, 열의 모든 숫자를 더해서(XOR) 한 숫자로 만든다.
이처럼 한 열을 숫자 하나로 바꾸는 작업이 MixColumn이다.
