이산대수 문제

어제 컴퓨터보안 중간고사 시험에 이산대수 문제에 대해서 기술하라는 문제가 나왔다.

기억이 가물가물해서 엉뚱한 답을 적었다.

시험 후 확인해 보았는데, 기억이 난다. (아래 수식의 mod m 에 대해서는 설명을 생략한다.)

y=xⁿ (mod m)

y, x 을 알고 있을때, 지수 n을 구하는 문제이다.

즉, 밑수 x의 거듭제곱n값을 알때 의 결과 y는 간단한 계산으로 구할 수 있으나,

반대로 결과y와 밑수x를 알때 거듭제곱 n의값 을 구하는 것은 간단히 계산되지 않는다는...

즉, 컴퓨터에서 Y=Xⁿ 의 Y값은 쉽게 컴퓨팅해서 알 수 있으나(단시간에 가능),

n = LOGx Y 의 n(지수)값은 쉽게 컴퓨팅해서 알 수 없다는(시간이 오래걸린다는) 원리를 암호화에 적용한 방법이 이산대수 문제이다.

정리하면, 컴퓨터연산에서 지수계산은 짧은 시간에 답이 나오지만, 로그계산은 시간이 길게 걸린다는 문제를 암호생성에 적용한다는 말.

암호학에서는 공개키 암호방식인 RSA알고리즘에서 사용되는 기본개념이다.

Ps. 한자 離散 대수는 떨어진 수 즉, 연속적이지 않은 수 즉, 디지털 수에 관한 대수(사칙연산)이다.

즉, 컴퓨팅 연산 = 디지털 연산과 이산대수는 같은 말이다. 쉬운말로 컴퓨터에서의 수식의 값 구하기 이다.

컴퓨터 연산에서의 문제라고 할 수 있다.