코딩 더 매트릭스 - 3장 벡터 (2)

벡터의 도트곱

2018년 11월 25일

필립 클라인의 저서 코딩 더 매트릭스 3장 벡터.


  1. 벡터의 도트곱을 이용해 간단한 유사성 측정과 인증기법 공격을 알아봅니다.
  2. 도트곱의 덧셈에 대한 분배성을 알아봅니다.
  3. Python으로 직접 Vec 클래스를 만들어 봅니다.





유사성 측정하기

하나의 짧은 오디오 클립이 긴 오디오 세그먼트에 나타나는지 검색하고자 합니다. 수학적으로 오디오 세그먼트는 파형이며 시간에 대한 연속함수 입니다. 정의역이 연속된 시간이라면, 공역은 진폭입니다. 진폭은 양수와 음수 사이를 진동합니다. 아래 표는 두 개의 오디오 세그먼트를 일련의 숫자들로 표현한 값입니다.

5 -6 9 -9 -2 3 5 7
5 -3 8 -1 2 6 5 -4

두 개의 오디오 세그먼트를 비교하는 가장 단순한 방법은 도트곱 i=1nu[i] v[i]\sum^{n}_{i=1}u[i]\text{ }v[i] 을 이용하는 것입니다. 각 엘리먼트 u[i]u[i]v[i]v[i]가 같은 부호라면 곱한 결과가 양수가 되고, 다른 부호라면 음수가 되니 도트곱이 클수록 비슷한 오디오 세그먼트라 할 수 있습니다. 두 세그먼트의 도트곱을 계산해보면 25+18+72+9+(4)+18+25+(28)=13525 + 18 + 72 + 9 + (-4) + 18 + 25 + (-28) = 135입니다. 만약 두 개중 하나의 오디오 세그먼트가 더 짧으면 어떻게 유사성을 측정할 수 있을까요? 다음 표들이 이 물음에 대한 답이 될 것 같습니다.

5 -6 9 -9 -2 3 5 7
5 -3 8 -1 0 0 0 0

5 -6 9 -9 -2 3 5 7
0 5 -3 8 -1 0 0 0

5 -6 9 -9 -2 3 5 7
0 0 5 -3 8 -1 0 0

5 -6 9 -9 -2 3 5 7
0 0 0 5 -3 8 -1 0

5 -6 9 -9 -2 3 5 7
0 0 0 0 5 -3 8 -1

짧은 오디오 클립의 0번째 위치를 옮기면서 빈 곳의 값은 0으로 바꿔 도트곱을 해줍니다. 위 표의 도트곱을 각각 구해보면 [124,127,53,20,14][124, -127, 53, -20, 14]로 첫번째 경우에 가장 유사합니다. 하지만 이런 방식을 모든 벡터에 대해 적용할 수는 없습니다. 예를 들어 세그먼트 [1,2,3,4,5,6][1,2,3,4,5,6][1,2,3][1,2,3]을 비교할 때, 다음 경우가 가장 큰 도트곱을 얻습니다.

1 2 3 4 5 6
0 0 0 1 2 3

이것은 분명히 잘못된 선택입니다.





도트곱을 이용한 간단한 본인 인증

GF(2)GF(2)필드 상의의 벡터 데이터를 주고 받는 서버와 밥(Bob)이 있습니다. 서버에 접속하기 위해 사용자는 패스워드로 본인임을 증명해야 합니다. 로그인 할때마다 사용자의 패스워드를 전달받아 서버에 저장된 값과 비교 검사하면 간단하지만 네트워크 상에 엿듣는 사람이 있다면 패스워드를 고스란히 노출하게 됩니다. 서버는 이를 방지하기 위해 간단한 인증 기법을 도입했습니다. 사용자에게서 직접 패스워드를 전달받지 않고 nn개의 벡터 a1,a2,...ana_1, a_2, ... a_n을 사용자에게 차례로 전달합니다. 벡터 ana_n과 패스워드 벡터 xx는 다음을 만족합니다.

a1x=β1a2x=β2...anx=βn\begin{aligned} a_1 \cdot x &= \beta_1 \\ a_2 \cdot x &= \beta_2 \\ & . \\ & . \\ & . \\ a_n \cdot x &= \beta_n \end{aligned}

서버는 벡터 aia_i를 사용자에게 전달할 때마다 사용자에게서 βi\beta_i를 응답받기를 기대합니다. 예를 들어 a1=[0,1,0,1,1],a2=[1,1,1,1,0]a_1 = [0, 1, 0, 1, 1], a_2 = [1, 1, 1, 1, 0] 일때 각각을 패스워드 x=[1,0,1,1,1]x = [1, 0, 1, 1, 1]와 도트곱한 값 β1=0,β2=1\beta_1 = 0, \beta_2 = 1입니다. 이 과정을 nn번 반복해 사용자의 본인 인증을 증명합니다.





도트곱의 분배성

동일한 차원의 임의의 벡터 uu, vv, ww가 있습니다. 도트곱의 다음 성질은 참입니다. (u+v)w=uw+vw(u + v) \cdot w = u \cdot w + v \cdot w u=[u1,u2,...un],v=[v1,v2,...vn],w=[w1,w2,...wn]u = [ u_1, u_2, ... u_n ], v = [ v_1, v_2, ... v_n ], w = [ w_1, w_2, ... w_n ] 이라 놓고 간단히 증명할 수 있습니다.

(u+v)w=[u1+v1,u2+v2,...un+vn][w1,w2,...wn]=(u1+v1)w1+(u2+v2)w2+...+(un+vn)wn=u1w1+v1w1+u2w2+v2w2+...+unwn+vnwn=u1w1+u2w2+...+unwn+v1w1+v2w2+...+vnwn=uw+vw\begin{aligned} (u + v) \cdot w & = [ u_1 + v_1, u_2 + v_2, ... u_n + v_n ] \cdot [ w_1, w_2, ... w_n ] \\ & = (u_1 + v_1)w_1 + (u_2 + v_2)w_2 + ... + (u_n + v_n)w_n \\ & = u_1 w_1 + v_1 w_1 + u_2 w_2 + v_2 w_2 + ... + u_n w_n + v_n w_n \\ & = u_1 w_1 + u_2 w_2 + ... + u_n w_n + v_1 w_1 + v_2 w_2 + ... + v_n w_n \\ & = u \cdot w + v \cdot w \end{aligned}

위와 같은 도트곱의 덧셈에 대한 분배성을 이용해 앞서 봤던 본인 인증 기법을 네트워크 공격자의 입장에서 살펴보겠습니다. 공격자가 a1=[0,1,0,1,1],a2=[1,1,1,1,0]a_1 = [0, 1, 0, 1, 1], a_2 = [1, 1, 1, 1, 0] 정보와 β1=0,β2=1\beta _1 = 0, \beta _2 = 1 정보를 탈취했다면 a1+a2=[1,0,1,0,1]a_1 + a_2 = [ 1, 0, 1, 0, 1 ]가 서버에서 aka_k값으로 전달됐을때 그 답 βk=1\beta _k = 1이라는 사실을 공격자는 알 수 있습니다. a1x+a2x=(a1+a2)xa_1 \cdot x + a_2 \cdot x = (a_1 + a_2) \cdot x라는 성질을 이용한 것입니다.





Vec 구현

벡터 덧셈, 스칼라곱, 도트곱 연산을 위해 직접 Vec 클래스를 만들어 보겠습니다. 그 전에 소스파일에서 vec.py를 다운받습니다. 이 파일은 크게 두 파트로 나눠져 있습니다. class Vec 코드 이전까지의 코드는 테스트 코드, 이후는 직접 써야할 Vec클래스 코드입니다. Python에서는 doctest라는 모듈을 제공하고 있습니다. 커맨드라인 인터페이스에서 Python코드를 작성하듯 각 테스트 함수마다 아래와 같은 테스트 코드를 작성하면 doctest모듈로 코드를 테스트할 수 있습니다.

def square(x):
    """Return the square of x.

    >>> square(2)
    4
    >>> square(-2)
    4
    """
    return x * x

테스트 코드 실행은 python -m doctest <파일이름.py> 명령어를 이용합니다. 아래 코드는 vec.py의 테스트를 모두 통과하는 Vec 클래스 코드 입니다.

class Vec:
    def __init__(self, labels, function):
        self.D = labels
        self.f = function

    def __repr__(self):
		"""
		Vec({...}, {...}) 인스턴스 혹은 인스턴스를 담은 변수를 호출했을때 문자열로 반환하는 값
		e.g.
		>>> v = Vec({...}, {...})
		>>> v
		Vec({...}, {...})
		"""
        return 'Vec(%s,%s)' % (self.D, self.f)

    def __str__(self):
		"""
		print 함수로 인스턴스 혹은 인스턴스를 담은 변수를 호출했을때 문자열로 반환하는 값
		아래 코드의 경우 다음과 같이 출력합니다.
		>>> v = Vec({1,2}, {1: 'a', 2: 'b'})
		1  2
		----
		a  b
		"""
        pad = 2
        max_len = max({ len(str(v)) for v in self.D } | { len(str(v)) for v in self.f.values() }) + pad
        sorted_D = sorted(self.D)
        key_line = ''.join([ str(d).rjust(max_len) for d in sorted_D ])[pad:]
        dash_line = ''.join([ '-' * max_len for i in range(len(sorted_D)) ])[pad:]
        value_line = ''.join([ str(self[d]).rjust(max_len) for d in sorted_D ])[pad:]
        return '%s\n%s\n%s' % (key_line, dash_line, value_line)

    def __getitem__(self, key):
		"""
		키값으로 값을 얻는 연산자 "[ ]" 정의
		"""
        return self.f[key] if key in self.f else 0

    def __setitem__(self, key, value):
		"""
		키값으로 값을 할당하는 연산 정의
		e.g. v[key] = value
		"""
        if key not in self.D:
            raise ValueError("key is not in D")
        self.f[key] = value

	def __add__(self, other):
		"""
		덧셈 연산자 "+" 정의
		"""
        return Vec(self.D, { d: self[d] + other[d] for d in self.D if self[d] or other[d] })

    def __neg__(self):
		"""
		음의 연산자 "-" 정의
		e.g. -v
		"""
        return Vec(self.D, { d: -self[d] for d in self.D })

    def __sub__(self, other):
		"""
		뺄셈 연산자 "-" 정의
		"""
        return self + (-other)

    def __mul__(self, other):
		"""
		곱셈 연산자 "*" 정의
		"""
        if isinstance(other, Vec):
            return sum([ self[d] * other[d] for d in self.D ])
        else:
            return Vec(self.D, { d: self[d] * other for d in self.D })
	"""
	mul : 매개변수 self는 "*" 의 왼쪽객체, other는 "*" 의 오른쪽객체
	rmul : 매개변수 self는 "*" 의 오른쪽객체, other는 "*" 의 왼쪽객체
	"""
    __rmul__ = __mul__

    def __floordiv__(self, other):
		"""
		나눗셈 연산자 "/" 정의
		"""
        return Vec(self.D, { d: self[d] / other for d in self.D })
    __truediv__ = __floordiv__

    def __eq__(self, other):
		"""
		일치 연산자 "==" 정의
		"""
        D = set(self.f.keys()) | set(other.f.keys())
        for d in D:
            if self[d] != other[d]:
                return False
        return True

	def copy(self):
		"""
		같은 주소값을 가리키는 객체가 아닌 내용은 같지만 완전히 다른 객체 생성(복사)
		"""
        return Vec(self.D.copy(), self.f.copy())

# 리스트를 벡터로
def list2vec(L):
    return Vec(set(range(len(L))), {k:L[k] for k in range(len(L))})

# 영벡터
def zero_vec(D):
    return Vec(D, {})

클래스의 각각의 메소드는 Python의 기본적인 연산들을 정의합니다. 각각의 메소드가 어떤 연산을 정의하는지 코드에 주석을 달아 놓았으니 참고하시면 좋겠습니다.