hoodbilen's warroom

이번 과제는 main문과 struct 구조만 알려준 채로, 해당 main문 내에 존재하는 함수를 구현하고 알맞게 출력하도록 코딩을 하는게 목표였다.

위에는 알려준 구조체와 전역 포인터 ptr이고,

위에는 알려준 main문이다.

필자가 구현해야 했던 함수는 총 9개로

첫번째 indexSet함수를 제외한 8개의 함수는 모두 main문에서 사용된다.

main문을 분석해보면

#7 해당 소스 실행파일은 인자를 정확히 두개만 받는다.

#21 argv[1]에 들어간 문장("iamacybersecuritygenius.")을 insert함수를 이용해 각각 한개씩 구조체로 만들어준다.

(+조건 :  새로 선언하는 구조체의 index는 항상 0으로 해줘야한다. ex) 마지막구조체(value = '.')의 index = 0)

#23 invert함수를 이용해 node방향을 뒤집어 준다.

(+조건 : 각각의 index도 전환해줘야한다. ex) 첫번째구조체(value = 'i')의 index = 0 )

#24 current라는  현재 위치의 포인트변수를 선언하고 ptr값을 넣은다.

#25 printList함수에 current값을 넣어 link를 따라가며 모든 value값을 출력한다.

#27 length함수에 current값을 넣어 현재 구조체의 개수를 구한다.

#28 readValue함수에 i값을 넣어 index가 i인 구조체의 value값을 뽑아준다.

#34 delete함수를 이용해 next에 할당된 구조체를 free해주고 current가 next 다음함수를 가르키도록 한다.

#42 search함수를 이용해 해당 문자가 value의 값인 구조체를 찾아 index를 리턴해준다. findNode함수를 이용해 해당 구조체의 포인터를 리턴해준다.

이제 해당 main문에서 출력되는 값과, 과제에서 주어진 조건을 맞춰 함수를 구성한다.

함수를 순서대로 보면,

indexSet함수는 index를 설정해주는 함수이다. 사실 Single Linked List구조에 대해 생각해보면 link만 잘 연결해 주면 될것 같은데 문제 난이도를 위해 index 설정 조건을 넣으신거같다.

insert함수를 구현할 때 node가 NULL일때와 NULL이 아닐때에 대해 고려해줘야하는 조건이 있었다. NULL일 경우에는 새로운 구조체를 만들고 전 구조체에 연결해주고, NULL이 아닐 경우에는 이미 존재하는 구조체 사이에 값을 넣어주는 것으로 구현해 줬다.

Single Linked List의 link방향을 뒤집어주는 invert함수를 구현한다.(조건에 index도 바꿔 줘야한다 했음으로 index도 재설정해줬다.)

link를 따라 각 구조체의 value값을 출력해주는 printList함수를 구현해줬다.

입력받은 포인터부터 구조체 link의 끝가지 넘어가며 총 Single Linked List의 길이를 구해주는 length함수를 구현해준다.

num값을 인자로 받아 index가 num인 구조체의 value값을 return 해주는 readValue함수를 구현해준다.

포인터 x를 인자로 받아 x다음 구조체를 free해주고 그 다음 구조체와 x의 link를 연결해주는 delete함수를 구현해준다.

data를 인자로 받아 구조체의 value가 data와 같은 구조체가 존재하면 해당 구조체의 index를 return해주고, 아닐 경우 -1을 return해주는 search함수를 구현해준다.

num값을 인자로 받아 해당 num 값이 index에 들어있는 구조체를 찾아서 해당 구조체의 주소를 return해주는 findNode함수를 구현해준다.

이것으로 모든 함수를 구현해 주었고, 출력값을 보면

이런식으로 출력됨을 볼 수 있다.

고전적인 하노이타워 문제변형을 풀어봤다.

기존 하노이타워 문제는 3개의 rod와 여러개의 disk가 존재하는데, 1rod에 존재하는 모든 disk를 3rod에 모두 옮기면 되는 문제이다. 단, disk의 크기는 모두 다르고, disk는 한번에 한 개씩 옮길 수 있으며,  큰 disk가 작은 disk 위에 올라가서는 안된다. 라는 조건이 들어가 있다.

위 문제의 코드를 작성하면,

이렇게 작성할 수 있다.

honoi는 재귀함수 방식을 쓰며, 해당 코드를 분석하면

#9 rod1에 있는 n-1개의 disk를 rod2에 옮긴다.

#10 rod1에 있는 마지막 disk를 rod3에 옮긴다.

#11 rod2에 있는 n-1개의 disk를 rod3에 옮긴다.

해당 코드의 출력값을 보면

이렇게 출력이 가능하다.

그럼 이제 하노이타워 변형문제에 대해 설명하겠다.

이번 문제는 disk를 옮길때 rod를 건너 뛸 수 없다는 조건이 들어간다. 말 그대로 rod1에서 rod3으로 옮기고 싶다면 반드시 "rod1에서 rod2", "rod2에서 rod3"이렇게 두번 출력해주어야 한다는 말이다.

해당 문제를 코드로 작성하면

이런식으로 작성할 수 있다.

해당코드를 분석하면

#10 rod1에 있는 n-1개의 disk를 rod3에 옮긴다.

#11 rod1에 있는 마지막 disk를 rod2에 옮긴다.

#12 rod3에 있는 n-1개의 disk를 rod1에 옮긴다.

#13 rod2에 있는 마지막 disk를 rod3에 옮긴다.

#14 rod1에 있는 n-1개의 disk를 rod3에 옮긴다.

해당 코드의 출력값을 보면

출력 마지막 부분을 보면 이동한 횟수가 나오는데, 해당 코드는 𝑇𝑛 = 3𝑇(𝑛−1) + 2 그리고 𝑇1 = 2. 를 따른다.

해당 수열을 정리하면,  이동한 최소 횟수는 𝑇𝑛 = 3^𝑛 − 1 를 따르는 것을 알 수 있다.

지난번 포스트에서 AES 복호화 코딩에 대해 기록했는데 이번에는 고속화에 대해 기록하려 한다.

해당 그림을 보면 Inv_Shift Row -> Inv_Sub Byte -> Add Round key -> Inv_Mix Column순서로 한 라운드를 돈다.

고속화의 핵심은 우선 8bit짜리 16개의 블록을 32bit짜리 4블록으로 묶고,  Inv_Sub Byte와 Inv_Mix Column연산을 묶은 Td테이블을 만들어 최대한 연산 수를 줄이는 것이다.

우선 Td 테이블을 제작한다.

Td[0]는 위 식에 기반해 S_box에 넣은 값과 연산하여 32bit로 만들어  256개의 원소를 가진 테이블을 제작한다.

위 방식대로 나머지 Td[1], Td[2], Td[3]도 마저 제작한다.

기본적인 세팅을 해준 뒤, AES_KeySchedule_32bit함수를 작성해준다.

RoundkeyGeneration128_32bit함수를 들어가면 대부분 RoundkeyGeneration128과 같지만 각각 8bit로 쪼개 주는 AES_KeyWordToByte함수가 없는 것을 알 수 있다.

이번엔 File_AES_Decryption_Optimization함수를 보자. 

위는 File_AES_Decryption_Optimization함수의 일부분이다. 초기벡터를 CT에 넣고 key인 W를 거꾸로 넣는 것이 불편해 앞, 뒤 숫자를 바꿔주는 코드를 넣었다.

이 뒤에 KeyMixcolumns해주었는데,  총 두 가지 방법으로 성공했다. 

첫 번째 방법은 키 W를 Td테이블에 SBox연산을 한 W를 넣는 방법이다.

두 번째 방법은 키 W를  AES_Inv_MixColumns에 넣고 돌리는 방법이다.

KeyMixcolumns을 해주는 이유는 복호화 순서가 Inv_Shift Row -> Inv_Sub Byte -> Add Round key -> Inv_Mix Column인데 가운데 Add Round key과정 때문에 Td테이블을 활용하기 위해 해 준 것이다. Mixcolumn은 선형연산으로 Mix(Sub_Byte^Add_Round_key)를 Mix(Sub_Byte)^Mix(Add_Round_key)로 분리할 수 있다. 해서 앞부분은 Td테이블을 활용, 뒤에는 KeyMixcolumns를 이용해 연산해준다.

KeyMixcolumns연산이 끝났다면 이제 본격적으로 128bit씩 파일에서 받아와 라운드를 돌리면 된다. 

AES_DEC_Optimization을 보면 아까보다 훨씬 라운드가 간단해진 것을 볼 수 있다. 첫 번째 라운드에서  s에 32bit씩 넣어 Add Round key를 해주고 9라운드를 돌아주면 된다. 각 라운드를 잘 보면 Td테이블 연산과 동시에 Inv_Shift Row도 해주는 것을 볼 수 있다. 9라운드를 돌고나면 마지막 라운드는 Inv_Mix Column연산이 없음으로 Inv_Shift Row, Inv_Sub Byte, Add Round key만 해준다.

마지막으로 AES_CBC만 해주면 복호화가 끝난다.

위 코드는 팀원 RyuH님의 도움으로 대부분 작성되었습니다~!

팀 프로젝트 과제로 AES 암호화 (key size : 128 bit)된 mp3 파일을 해독하여 노래 제목을 찾는 과제가 나왔다.

조건은 이 정도.

u8과 u32를 설정해주고

위 함수로 inv_Sbox를 생성해 준다. 

inv_Sbox를 코드에 넣어주고

main 문 작성. mp3파일을 올려야 해서 fp사용.

File_AES_Decryption 함수를 작성. 기본적인 CT, PT, IV(초기 벡터), MK, RK, keysize 등을 설정해준다.

AES_KeySchedule에서  key가 128bit임으로 RoundkeyGeneration128 함수로 건너뛰어서 함수를 작성한다.

Rcon을 설정해주고,

AES_RotWord(key shift column)와 AES_SubWord(Sbox 대입)를 설정해준다.

AES_Roundkey_4words_generation로 각 라운드 키를 마저 만들어주고,

AES_KeyWordToByte로 32bit로 묶여있던 W배열을 8bit로 다시 쪼개 준다.

AES_KeySchedule을 다 수행했으므로 다시  File_AES_Decryption로 돌아간다.

현재 CBC모드로 암호화가 되어있기 때문에 CT에 초기 백터를 넣어준 후, 파일을 128bit만큼 각각 쪼개서 파일이 끝날 때까지 while문을 돌려 복호화해주는 방식으로 코드를 작성했다.

AES_DEC 코드를 보면 AES_LRound(AES_Inv_MixColumn 없음), AES_Round, AES_Inv_AddRoundKey 순서로 함수를 돌면서 복호화되도록 코드를 작성했다.

마지막으로 AES_CBC를 돌면서 복호화가 끝난다.

위 코드는 팀원 RyuH님의 도움으로 대부분 작성되었습니다~!