2016의 게시물 표시

블록 암호 운용 방식

이미지
초기화 벡터 초기화 벡터(initialization vector, IV)는 첫 블록을 암호화할 때 사용되는 값을 의미한다.
운용 방식마다 초기화 벡터를 사용하는 방법이 다르며 초기화 벡터에서 요구되는 성질도 조금씩 다를 수 있지만, 같은 초기화 벡터가 반복되어 사용되어서는 안 된다는 성질을 공통적으로 가진다. 이것은 초기화 벡터가 같은 경우 비슷한 두 개의 평문을 암호화했을 때 앞부분의 블록들이 서로 같게 되는 등 보안 문제가 발생하기 때문이다.
CTR 등의 일부 운용 방식에서는 초기화 벡터라는 용어 대신 nonce(number used once)라는 용어를 사용한다. 이 표현은 보통 초기화 벡터가 매번 달라야 하는 것 외에 별다른 요구 조건이 없을 경우 사용한다.


전자 코드북 (ECB) 전자 코드북(electronic codebook, ECB)은 운용 방식 중 가장 간단한 구조를 가지며, 암호화하려는 메시지를 여러 블록으로 나누어 각각 암호화하는 방식으로 되어 있다.

전자 코드북은 모든 블록이 같은 암호화 키를 사용하기 때문에 보안에 취약하다. 만약 암호화 메시지를 여러 부분으로 나누었을 때 두 블록이 같은 값을 가진다면, 암호화한 결과 역시 같다. 이것은 공격자가 비슷한 메시지를 반복적으로 암호화하는 반복공격에도 취약한 성질을 가진다.


암호 블록 체인 방식 (CBC) 암호 블록 체인 (cipher-block chaining, CBC) 방식은 1976년 IBM에 의해 개발되었다.[4] 각 블록은 암호화되기 전에 이전 블록의 암호화 결과와 XOR되며, 첫 블록의 경우에는 초기화 벡터가 사용된다. 초기화 벡터가 같은 경우 출력 결과가 항상 같기 때문에, 매 암호화마다 다른 초기화 벡터를 사용해야 한다.

CBC 방식은 현재 널리 사용되는 운용 방식 중 하나이다. CBC는 암호화 입력 값이 이전 결과에 의존하기 때문에 병렬화가 불가능하지만, 복호화의 경우 각 블록을 복호화한 다음 이전 암호화 블록과 XOR하여 복구할 수 있기 때문에 병렬화가 가능하다.


증식적 암…

Error converting bytecode to dex

안드로이드 스튜디오에 자바 라이브러리 모듈을 추가했는데, 시스템에 설치된 JDK는 8인데 반해서, 안드로이드 컴파일시에 요구되는 자바 버전은 7이다.

그저 아무 생각없이 시스템에 JDK 7을 설치해 버릴까 하다가,
오류 메시지를 한 번 더 자세히 읽어 보니,
자바 라이브러리 모듈의 build.gradle 파일에 다음 두 줄을 추가해 주라고 한다.

apply plugin: 'java' targetCompatibility = '1.7' sourceCompatibility = '1.7'

Unmappable character for encoding MS949

안드로이드 스튜디오에서 자바 라이브러리 모듈을 하나 추가했더니
unmappable character for encoding MS949
라는 컴파일 오류가 뜬다. 그냥 주석에 한글 몇 자 있을 뿐인데도 이걸 처리하지 못한다.

원인:
자바 파일의 인코딩은 UTF-8을 사용하고 있는데, 윈도우즈 시스템의 기본 인코딩이 MS949라서 그렇다고 한다.

해결 방법:
자바 라이브러리 모듈의 build.gradle 파일을 열고 다음과 같이 한 줄을 추가해준다.
apply plugin: 'java' compileJava.options.encoding = 'UTF-8'

좌표 변환: 회전 이동

이미지
아래 그림에서와 같이, 원래의 좌표를 (x, y)라 하고, y축으로부터의 각도를 θ라고 하자. 또, 회전 시키고자하는 각도를 δ라 하고, 회전된 좌표를 (x', y')라고 한다.
이 때, 회전의 기준점과 원래의 좌표 사이의 거리를 r이라고 하면, 회전된 이후의 좌표와 회전 기준점 사이의 거리 또한 r로써 동일하다.

수식으로 정리하면,
x = r sinθ
y = r cosθ

x' = r sin(θ+δ)
y' = r cos(θ+δ)

삼각함수의 덧셈정리를 이용하여 x'와 y'를 풀어보면,

x' = r (sinθ cosδ + cosθ sinδ)
   = r sinθ cosδ + r cosθ sinδ
y' = r (cosθ cosδ - sinθ sinδ)
   = r cosθ cosδ - r sinθ sinδ

x = r sinθ, y = r cosθ이므로,
x' = x cosδ + y sinδ
y' = y cosδ - x sinδ

δ가 반시계방향인 경우에는,
x' = x cosδ - y sinδ
y' = y cosδ + x sinδ
라는 수식으로 정리될 수 있다.


이렇게 구한 공식을 도형의 각 꼭지점에 대해서 적용하면 회전 이동한 도형을 구할 수 있다.

public void rotateBy(float d, float x0, float y0) { float dX = x - x0; float dY = y - y0; double rad = Math.abs(Math.toRadians(d)); float cosD = (float) Math.cos(rad); float sinD = (float) Math.sin(rad); if (d>=0) { x = dX * cosD + dY * sinD; y = dY * cosD - dX * sinD; } else { x = dX * cosD - dY * sinD; y = dY * cosD + dX * sin…

좌표 변환: 대칭 이동

이미지
점에 대한 대칭 이동 대칭 이동의 기준점과 도형의 꼭지점 사이의 거리를 구한다음, 기준점을 지나 그 거리만큼 더 이동하면 대칭 이동한 점의 좌표를 구할 수 있다.
우선, 기준점과 다각형의 각 꼭지점들 간의 거리 dx와 dy를 구한다.
각각의 꼭지점에 대해서 평행 이동한 다음 이동한 점들을 연결하면 대칭 이동한 도형을 얻을 수 있다.

축에 대한 대칭 이동 x축과 나란한 축에 대한 대칭의 경우에는 각 꼭지점의 x좌표는 변하지 않고 y좌표만 대칭 이동하면 된다.
마찬가지로, y축에 나란한 축에 대한 대칭의 경우에는 각 꼭지점의 y좌표가 변하지 않는다.
위 그림에서 왼쪽은 점에 대한 대칭 이동이며, 오른쪽은 직선에 대한 대칭이동이다.
그려놓고 보니 점에 대한 대칭 이동은 회전 이동과 같은 결과가 되었다.

좌표 변환: 스케일

이미지
평면 상의 어떤 도형의 크기를 변경하기 위해서는 도형을 구성하는 꼭지점의 좌표 이외에도 배율을 나타내는 scale factor와 크기 변경의 기준점 좌표도 알아야 한다.

Scale factor는 1.0을 기준으로 이보다 크면 확대, 작으면 축소로 가정한다.

우선, 도형의 각 꼭지점 좌표와 기준점 좌표 사이의 거리(d)를 구한다. 이 때, x 성분과 y 성분을 분리하는 것이 좋다.

이렇게 구한 각각의 거리 값에 배율을 곱한다. 그러면, 기준점으로부터 계산된 거리만큼을 이동한 새로운 점의 좌표를 얻을 수 있고, 이 좌표들은 크기가 변환된 새로운 도형의 꼭지점들이다.
위 그림에서는 크기 변경의 기준점을 붉은 색으로 표시했으며, 왼쪽에서는 조형의 가운데에, 오른쪽에서는 왼쪽 아래에 각각 지정하였다. 파란색 사각형을 2배 크기로 확대한 도형이 초록색 도형이다.


어떤 도형의 크기를 s배로 변경하는 것은 기준점에서 도형의 각 꼭지점 까지의 거리를 s배로 변경하는 것이다.

좌표 변환: 이동

이미지
평면 상의 어떤 도형을 x방향으로 dx만큼, y 방향으로 dy만큼 이동하려는 경우,
다각형의 각 꼭지점(원의 경우에는 중심점을) 좌표 (x, y)에 dx, dy를 더한다.

즉, 점 (x, y)을 dx, dy만큼 이동한 새로운 점의 좌표를 (x', y')라고 할 때,
x' = x + dx
y' = y + dy
이다.

이를 각 꼭지점에 대해서 수행하면 평행이동된 도형을 구할 수 있다.

충돌 체크: Circle vs Circle

이미지
원과 원의 충돌 테스트는 의외로 간단하다.
우선, 피타고라스의 정리를 사용해서 원의 중심점 간의 거리를 구한다.

중심점 간의 거리가 두 반지름의 합보다 크면, 두 원은 서로 충돌하지 않은 것이다.중심점 간의 거리가 두 반지름의 합보다 작으면, 두 원은 서로 충돌한 것이다.중심점 간의 거리와 두 반지름의 합이 같다면, 두 원은 서로 붙어 있는 경우이다.

충돌 체크: Oriented Bounding Box

이미지
이전 글 AABB에 이어서,
위의 그림과 같은 경우 AABB 테스트에서는 충돌로 판정된다.
하지만 이것은 우리가 원하는 충돌 판정이 아니다. 따라서, 필요하다면 Oriented Bounding Box 방식으로 보다 세밀하게 충돌 판정을 해 줄 필요가 있다.
OBB란 바운딩 박스가 회전 되어서 좌표축에 나란하지 않다는 얘기다.


OBB 방식의 충돌 문제를 구현하기 위한 여러 방식들 가운데 SAT라는 것이 있다.
Separating Axis Theorem
두 개의 바운딩 박스가 서로 충돌하지 않는다면, 둘 사이를 가르는 직선이 존재한다. 바꾸어 말하자면, 둘 사이를 가르는 임의의 직선이 존재한다면, 두 개의 바운딩 박스는 서로 충돌하지 않는다고 할 수 있다.
위 그림에 그린 임의의 붉은 직선이 Separating Axis이다.
Separating Axis에 직교하는 다른 직선에 바운딩 박스를 투영시켜 보자. 이 때 직선 상에 투영된 두 개의 선분이 서로 겹치지 않는다면 두 개의 바운딩 박스는 서로 충돌하지 않는다고 말할 수 있다.

그렇다면,
Separating Axis는 어떻게 찾을 것인가. 라는 새로운 문제를 맞이하게 된다.

Separating Axis는 다각형을 구성하고 있는 변들 중 하나 이상과 나란하다.
절차
바운딩 박스를 구성하는 변들 중 하나를 선택해서,
그 변과 나란한 가상의 축에 직교하는 임의의 축을 가정하고,
그 축에 바운딩 박스를 투영시킨다.
만일, 두 개의 선분이 겹치지 않으면 서로 충돌하지 않음으로 판정하고 종료,
두 선분이 서로 겹친다면 다른 변을 선택해서 반복 수행.

사각형 vs 사각형의 문제인 경우 최대 8개의 축에 대해 충돌 테스트를 시행해 보아야 한다. 그러나, 위 그림과 같이 서로 나란한 변이 있다면 시행 횟수는 줄어든다.



[Tip]
OBB는 직사각형이 아니어도, 다각형이어도 적용 가능하다. 그러나, 모서리가 안쪽으로 파인 모양에는 적용이 안된다.

[참고]
http://www.dyn4j.org/2010/01/sat/


충돌 체크: Axis Aligned Bounding Box

이미지
게임 개발에서 충돌 테스트의 가장 기본적인 전략은 AABB인데, Axis Aligned Bounding Box란 좌표 축에 나란한 사각형으로서, 캐릭터를 감싸는 최소한의 너비와 높이를 가진 직사각형이다.
두 개의 좌표축에 나란한 직사각형이 조금이라도 서로 겹치는지를 판단하면 된다.

바운딩 박스 A의 최대 x 좌표(right)가 바운딩 박스 B의 최소 x 좌표(left)보다 작으면 충돌이 아니다.바운딩 박스 A의 최소 x 좌표(left)가 바운딩 박스 B의 최대 x 좌표(right)보다 크면 충돌이 아니다.바운딩 박스 A의 최대 y 좌표(top)가 바운딩 박스 B의 최소 y 좌표(bottom)보다 작으면 충돌이 아니다.바운딩 박스 A의 최소 y 좌표(bottom)가 바운딩 박스 B의 최대 y 좌표(top)보다 크면 충돌이 아니다. 이를 자바 코드로 작성하면 다음과 같다. 참 쉽다, 비교 몇 번이면 끝난다.
public static boolean checkAABB(RectF a, RectF b) {return a.right > b.left && a.left < b.right && a.top > b.bottom && a.bottom < b.top; }
그런데, 아래 그림에서처럼 캐릭터가 회전을 한다거나 하는 경우에는 정확도가 떨어진다는 단점이 있다. 다음 글에 이어서...