Earticle

지금까지는 Pollard의 Rho 알고리즘이 대칭키의 암호를 해독하는 이산대수 문제에 대해 가장 효율적인 방법으 로 알려져 있다. 그러나 이 알고리즘은 거인걸음 보폭 m = 「 p 」개의 데이터를 저장해야 하는 단점과 더불어 O( p ) 수행 복잡도를 보다 감소시킬 수 있는 방법에 대한 연구가 진행되고 있다. 본 논문은 이산대수의 사이클 검출을 위한 Nivasch의 스택 법의 데이터 갱신 횟수를 73% 이상 감소시키는 배열법을 제안하였다. 제안된 방법은 배열을 적용하였으며, ( xi < 0.5xi-1) ∩ (xi < 0.5(p-1)) 인 경우에 한해 배열 값을 갱신하는 방법을 적용하였다. 제안된 방법은 스택법과 동일한 모듈러 연산횟수를 보였지만 스택 법에 비해 이진탐색 법을 적용하여 배열 갱신 횟수와 탐색 시간을 획기적으로 감소시켰다.

Until now, Pollard's Rho algorithm has been known as the most efficient way for discrete algebraic problems to decrypt symmetric keys. However, the algorithm is being studied on how to further reduce the complexity of O( p ) performance, along with the disadvantage of having to store the giant stride m = 「 p 」 data. This paper proposes an array method for cycle detection in discrete logarithms. The proposed method reduces the number of updates of stack memory by at least 73%. This is done by only updating the array when ( xi < 0.5xi-1) ∩ (xi < 0.5(p-1)). The proposed array method undergoes the same number of modular calculation as stack method, but significantly reduces the number of updates and the execution time for array through the use of a binary search method.

본 논문에서는 소프트웨어 구동 시 발생 가능한 메모리 오류 중 발생 빈도가 매우 낮은 일부 메모리 오류에 대해 실행 파일을 역어셈블하여 만들어진 어셈블리어의 구문을 분석하여 메모리 오류 가능성을 검출하는 방법을 제안한다. 몇 개의 프로그램을 대상으로 선정하고, 제안한 방법을 이용하여 메모리 오류 가능성을 검출한 결과, 약 만 개의 함수, 백만 라인의 어셈블리어 명령어에서 750여 개의 메모리 오류 가능성을 검출하였고, 검출에 걸린 시간은 총 90초 정도가 소요되었다.

This thesis proposes a method for effectively detecting memory errors with low occurrence frequency that may occur depending on runtime situation by analyzing assembly codes obtained by disassembling an executable file. When applying the proposed method to various programs having no compilation error, a total of about 750 potential errors taken about 90 seconds are detected among 1 million lines of assembly codes corresponding to a total of about 10 thousand functions.