ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • AES암호화 (Rijndael 알고리즘)
    알고리즘/알고리즘 개념 및 정리 2018.01.25 01:47


    WPA2에 AES암호화가 사용된다고 해서 공부 중에 있다. 


    AES (Advanced Encryption Standard)


    AES 암호화는 Rijndael 알고리즘을 기반으로 만들어진다.


    직접 구현을 해보았고 그렇게 오래 걸리진 않았으나 아직도 AES 암호화에 대해서는 완벽하게 공부가 되지 않았다.


    Rijndael 알고리즘의 원리를 이해하기 위해서는 몇가지 지식이 필요하다.


    1. xor 연산 (계산기를 이용하면서 보면 훨씬 좋다 http://xor.pw/#)

    2, 4x4 행렬 연산


    또한 이 알고리즘에서는 + 가 xor로 대체되어서 사용된다.


    나와 상대방만 알고있는 비밀키(cipher key)라하며 우리가 암호화할 평문을 Plain Text라 한다

    이 예제에서는 내가 정한 Plain Text와 Cipher Key를 아래와 같이 정의하였다.


      Plain Text                                            Cipher Key


    1. Rijndael 알고리즘

    원리는 4가지로 구분된다.


    1) Add round key

    Plain Text 와 Cipher Key를 XOR 연산한다.






    2) Sub Byte

    이 연산은 8비트 단위로 데이터를 치환해주는 연산이며 실제 연산은 1바이트를 GF(2^8) 에서의 역원을 이용하여 아핀 변환을 하는 연산이다.

    이렇게 변환된 값들은 비선형적인 값이 되어 암호를 더욱 풀기 어렵게 해준다. 이것이 가능한 이유는 앞서말한 GF(2^8)필드에서 곱셈에 대한 역원을 사용하기 때문이다.


    S-BOX

    .


    Sub Byte 연산




    3) Shift Row

    행을 단위로 하여 Shift 연산을 진행하면 된다.




    4)Mix Column

    각각의 바이트에 특정행렬과 곱셈 연산을 진행한다. 많은 사람들이 여기서 많이 헷갈려 할수도 있다.

    암호화에 사용되는 특정행렬은 다음과 같다.



    위의 행렬과 세로열 한줄씩 곱셈을 진행한다. 이 때 사용되는 개념이 행렬의 곱셈이다.



    설명을 하자면 이 행렬의 곱셈은 가로와 세로로 곱해진 후 한칸을 채우게된다.

    2 * 0x93 + 3 * 33 + 1 * 0xFC + 1 * 0x82 = 0x16이 되는데 이 때 그냥 계산해서는 안되고 + 는 XOR로 해야하며

    이런식의 곱셈이 진행되다 보면 256이 넘는수가 발생하게 된다.

    한 칸에 255까지의 수가 담길수 있음으로 256을 넘게되면, 즉 캐리가 발생되게 되면 

    ex) 0001 1111 1010 -> 이런식이 되면 앞의 1을 때버린다.(10진수로 계산할것이면 -256를 해준다)

    -> 1111 1010 그 후 0x1b와 XOR 연산을 진행해야 한다. 


    또한 3을 곱해주는 경우에 2번을 곱했는데 256을 넘기는경우 

    ex) 3 * 0xDF 이 경우는

    2 * 0xDF를 먼저 진행하면 0x1BE로 256을 넘기기 때문에 256을 빼준뒤 -> 0xBE에 남은 0xDF를

     단순히 더하는 것이 아니라 XOR연산을 해주어야 한다.

    이런식으로 진행하면 된다.






    2. key scheduling 키확장이라고도 한다.




    우선 마지막 4바이트를 한칸 쉬프트 한후 Sub Byte 연산을 진행한다

    (s-box를 보고 한다. 해당표를 가로열부터 따라가면 된다)

    ex) 23 -> 26이 된다. 


    S-BOX

    .


      


      쉬프트                                               SubByte






    해당 과정이 끝나면 Rcon과 한 세로줄씩 XOR연산을 해주면 된다.


    Rcon


    Rcon 과 XOR 연산




    그 다음은 Cipher Key의 첫번째 세로열과 XOR연산을 진행한다. 그렇게 완성된 열은 Round Key의 첫번째 세로열이 된다.






    그렇게 완성된 첫번재 세로열과 Cipher Key의 두번째 열얼 XOR하면 Round Key의 두번째 세로열이 된다. 

    이걸 두번 더(세번째,네번째 세로열) 반복하면 첫번째 Round Key가 완성된다.





    완성된 첫번째 Round Key


    이제 이렇게 완성된 Round key와 위에서 완성된 Mix Columns를 XOR연산을 진행한다. 그렇게 되면 Round1이 된것이다.

     이러한 Round를 9번까지 진행해야하고 

    마지막 Round10은 MixColumn을 진행하지 않는다. ShiftRows 후 10번째 Round Key와 XOR연산을 해주면 Cipher Text가 되는 것이다.


    이해가 되지 않는다면 테스트 사이트에서 글을 읽고 테스트 사이트에서 한번 구동시켜 보면 이해가 될 것이다.


    Rijndael 테스트 사이트 : http://www.formaestudio.com/rijndaelinspector/archivos/inspector.html

    :https://www.hanewin.net/encrypt/aes/aes-test.htm


    암호방식 :

    https://ko.wikipedia.org/wiki/%EB%B8%94%EB%A1%9D_%EC%95%94%ED%98%B8_%EC%9A%B4%EC%9A%A9_%EB%B0%A9%EC%8B%9D


    맨아래의 Flash를 보면 이해하는데 도움이 된다.(ENTER 키로 진행하면된다)


    마지막으로 위의 내용을 코딩으로 만들어 보았고 성공했다 ㅎㅎ


    그렇게 어렵지는 않았지만 뭔가 이해못한 내용이 있을 것만 같다. 좀더 고민해봐야겠다.


    그림1은 내가만든 코드로 완성시킨 것이고 그림2는 내가만든 코드결과를 테스트 사이트에서 확인한 것이다.

    AES암호가 필요하여 공부하였지만 암호화에 대해서 약간은 알게 된 것같아 기분이 좋다ㅎ

    다음엔 복호화를 성공시키고 포스팅해보겠습니다.

    (혹시나 잘못된 내용이나 질문은 댓글로 남겨주세요)


    그림 1


    그림 2









    '알고리즘 > 알고리즘 개념 및 정리' 카테고리의 다른 글

    퀵 정렬 Quick Sort  (0) 2019.03.09
    삽입정렬 Insert Sort  (0) 2019.03.07
    버블 정렬 Bubble Sort  (0) 2019.03.07
    선택정렬 Selection Sort  (0) 2019.03.07
    AES 복호화 (Rijndael 알고리즘)  (3) 2018.01.26
    AES암호화 (Rijndael 알고리즘)  (3) 2018.01.25

    댓글 3

    • 프로필사진

      Mix Column 계층에서 처음에2 * 0x93 + 3 * 33 + 1 * 0xFC + 1 * 0x82 = 0x16
      이부분에서 계산을 아무리 해봐도 16진수 16이 나오지가않습니다. 어떻게해서 저렇게나오는건가요 그후에 뒤에

      한 칸에 255까지의 수가 담길수 있음으로 256을 넘게되면, 즉 캐리가 발생되게 되면

      ex) 0001 1111 1010 -> 이런식이 되면 앞의 1을 때버린다.(10진수로 계산할것이면 -256를 해준다)

      -> 1111 1010 그 후 0x1b와 XOR 연산을 진행해야 한다.

      이부분에서 무조건 캐리가 발생되서 앞에1 을빼면 그후 무조건16진수 1B와 XOR을해야하나요

      2가지 부분에대해서 잘모르겠습니다 알려주시면 감사할거같습니다

      2018.07.10 09:32
      • 프로필사진

        캐리가 발생하면 무조건 0x1b와 xor 해야하는 것으로 알고 있습니다. 그렇지않으면 값이 이상하게 계산될 것입니다.
        저기 걸려있는 링크시뮬레이터로 돌려보시고 자신의 계산과 비교해보시면 좋을 것 같습니다.

        2018.08.05 19:54
    • 프로필사진

      너무 잘읽었습니다. 감동~

      2018.10.26 11:47
Designed by Tistory.