Taessing

ap-1 = 1(mod p)

also known as Fermat’s LittleTheorem

An alternative form of Fermat’stheorem is also useful

ap =a(mod p)

This form does not require that a be relatively prime to p

aø(n) = 1 (mod n)

for any a,n where gcd(a,n)=1 a와 n 은 서로소 이다.

if n is prime and gcd(a,n)=1, this is Fermat’s theorem. That is, aø(n) = an-1 = 1 (mod n)

n이 소수라면 페르마 정리랑 같아 진다.

eg.

a=3;n=10; ø(10)=4;

  hence34 = 81= 1 mod 10

a=2;n=11; ø(11)=10;

  hence210 =1024 = 1 mod 11

Alternative form of the Euler’s theorem also useful.

aø(n)+1 = a (mod n), where gcd(a,n)=1 a,n은 서로소 이다.

The probabilistic tests:

Most popular primality tests areprobabilistic tests

가장 유명한 테스트가 바로 확률 테스트다

These tests use, apart from thetested number n, some other numbers a which are chosen at random from some sample space

이 테스트들은 사용되는데 테스트 되는 숫자 n 과 다른 숫자 a가 서로 떨어진다. a 어떤 샘플 공간에서 랜덤적으로 선택이된다.

The usual randomized primality tests never report a primenumber as composite, but it is possible for a composite number to be reportedas prime

일반적으로 랜덤화하는 소수 테스트는  소수가 합성수로 보고가 되지 않는다, 하지만 합성수가 소수로 보고 되는 가능성이있다.

The probability of error can bereduced by repeating the test with several independently chosen as; for two commonly used tests

에러를 없애기 위해서 테스트 어떤 독립적인 선택된수 as 와 함게 반복적으로 테스트를 행한다; 두개의 널리쓰이는 테스트들이 있다.

For any composite n at least half the as detect n 's compositeness, so krepetitions reduce the error probability to at most 2−k, which can be made arbitrarilysmall by increasing k.

어떤 합성수 n은 적어도 aS의 절반이고 n의 합성수가 ?? 그래서 에러를 줄인다 뭐 이런 내용인듯??

• Key size는 128, 192, 256 비트이다.
• Block size는 128 비트 이다.(DES의 두배로군)
• 다양한 하드웨어에서 동작한다.
  
• 빠르다.
• 암호가 강력하다.

designed by Rijmen-Daemen in Belgium

has 128/192/256 bit keys, 128 bit data

an iterative rather than feistel cipher

treats data in 4 groups of 4 bytes

operates an entire block in every round

designed to be:

resistant against known attacks

speed and code compactness on many CPUs

design simplicity

• 데이터 프로세스가 4바이트의 4개의 그룹으로서 된다.(32*4=128비트)
• 초기의 XOR 연산이 있다.
• 9/11/13 라운드들에서는 아래와 같은 것들이 실행이 된다.

• 각 마지막 라운드(10/12/14)에서는 mix column 이 없다.
• 모든 오퍼레이션이 XOR과 Table lookup으로 되서 빠르고 효율적이다.

AES 파라미터를 보면

키의 크기에 따라서 라운드 수와 확장되는 키의 크기가 다른것을 알 수가 있다.
이제 본격적인 알고리즘에 들어가보자.
우선 전체적인 진행 과정을 볼 수있는 그림을 보도록 하자.

보면 처음에 128비트의 데이터가 들어가게 되면 AddRoundKey를 하게 되고 그다음에 128비트 데이터기준으로 라운드가 총 10번 돌게 된다 0~9번 라운드까지는 byte substitution, shiftrows, mixcolumn, Addroundkey를 하고 마지막 라운드에서는 mixcolumn은 빠지게 된다.
10번의 라운드가 끝나면 암호문이 나오게 된다.

일단 그림에서 알 수 있듯이 DES와는 다르게 16진수 개념이 많이 출현 하는데 16진수한자리당 4비트를 할당받는다는것을 기본으로 알고 가야한다.
Key나 데이터를 나타내는 형식 역시 테이블인데 16진수 2자리(8비트) 16개의 테이블이 된다는 것을 알 수 있다. 다음과 같이 나타낸다.

요런식으로 4*4 테이블로 나타낼 수 있다.

이제 각라운드에 쓰이는, byteSub, Shiftrows, mixcolumn, AddRoundKey 에 대해 알아보자.

1. byteSub
이건 DES의 초반 IP와 비슷하지만 좀 다르다. IP에서는 비트의 위치를 바꿔주는건데 이건 아무래도 테이블 형식으로 테이터가 구성되어 보이게 해놓았으므로 조금 다른데 그래도 쉽다.
S-box를 이용하는데 S-box는 다음과 같다.

흠 여기서 예를 들어 보자
0xCB라는 수는 S-box에 들어가면 어떻게 될 것인가? S-box가 행렬 제일 밖에 x,y를 표시를 해놓았다. 그렇다.
xy순서대로 그대로 찾으면 된다. x=C 이므로 C번째 행, y=B이므로 B번째 열  그렇게 찾으면 0x1F라는 수를 찾을 수 있다. 이렇게 잘찾아서 바꿔 주면 된다. 쉬운 것이지. 예를 보면

위와 같다. 그냥 열심히 테이블을 보고 바꿔주면 되는작업이 byteSub이다.


2.Shift row
그냥 열을 Shift하는데.
첫번째 행은 변화가 없다.
두번째 행은 1번 왼쪽으로 시프트
세번째 행은 2번 왼쪽으로 시프트
네번째 행은 3번 왼쪽으로 시프트
이것이 다다.

왼쪽 시프트가 된다는 점을 명심하고 1~4행 은 0~3번 시프트 된다.



3. MixColumn
이부분은 이산수학적인 지식이 좀 있어야 한다.
GF(2^8) 체계로 계산을 해야 한다. 그리고 행렬의 곱으로 나타낼 수 있는데
min poly = x^8 + x^4 + x^3 + x + 1 이것을 이용해야 하는데. 이것은 오버플로우가 날 때 더해주면 그값이 나오기 떄문에 편리하다. 오버플로우란 말은 x^9이상이 발생한다는 말이다. 이것은 계산을 해보면 알 것이다.

각열을 2 3 1 1
          1 2 3 1
          1 1 2 3
          3 1 1 2
와 곱해준 값이 바로 mixcolumn의 값인 것이다.

4. Roundkeyaddition
이것은 그냥 Roundkey 값과 XOR 연산을 해주면 된다.


이제 AES의 Key Expansion 키확장에 대해서 알아보자.
128비트의 키를 44 32-bit words
192비트의 키를 52 32-bit words
256비트의 키를 60 32-bit words
로 각각 확장이 된다.

확장된 키는 각라운드에서 쓰이게 된다.
이건 플래시 파일을 참조하도록하자.

rijndael_ingles_2004-kimsumin75.exe