[2021/08/20][짤막한 이야기 - 콜라츠 추측]

[2021/08/20][짤막한 이야기 - 콜라츠 추측]
“콜라츠 추측(Collatz Conjecture)”이란, 추측이라는 글자에서 알 수 있듯이 현재까지 풀리지 않은 난제이다.
개념은 간단하다.
1) 특정 수 N이 1이라면 이 알고리즘은 종료된다. (C(1) = Exit)
2) 특정 수 N이 (1이 아닌) 홀수라면 3을 곱한 후 1을 더한다. (C(N) = 3N + 1)
3) 특정 수 N이 짝수라면 2를 나눈다. (C(N) = N / 2)
이 과정을 반복하면 유한번의 재귀를 통하여 1에 도달한다는 것이 콜라츠 추측이다.
이 추측은 아직 1로 도달하지 않는 반례가 나오지 않았기 때문에 지속적으로 반례를 찾고있으며,
반대로 항상 이것이 성립한다는 증명도 되지 않았기 때문에 난제로 불리우고 있다.
암호학에서 소수가 중요하게 여겨지듯이, 소프트웨어 보안, 특히 난독화(Obfuscation)에서는 이러한 난제가 매우 중요하게 여겨진다.
자동화된 현대 분석 기술 중 많이 활용되는 “기호 실행(Symbolic Execution)”이나 “오염 분석(Taint Analysis)”으로도 그 근원을 파악하기 어렵기 때문이다.
즉, 사람이라면 콜라츠 추측이 포함된 보호 기법을 인지할 수 있지만, 컴퓨터(분석 도구)는 인지하지 못한 채 엄청난 양의 연산을 수행하게 되어 분석에 방해받을 수 있다.
[관련된 짤막한 이야기 - 동적 분석 & 정적 분석[2021/02/18]]
#이야기 #루니프 #콜라츠추측 #난제 #소프트웨어보안 #난독화 #소수 #암호학

[2021/08/20][Short Story - Collatz Conjecture]
"Collatz Conjecture" is an unsolved challenge, as the word "Conjecture" suggests.
The concept is simple.
1) If a certain number of N is 1, this algorithm is ended. (C(1) = Exit)
2) If a certain number N is an odd number (other than 1), multiply by 3 and add 1. (C(N) = 3N + 1)
3) If a specific number N is an even number, divide it by 2. (C(N) = N / 2)
The Collatz conjecture is that repeating this process leads to 1 through a finite number of recursions.
This conjecture is constantly seeking counter-examination because there is no counter-examination that has yet to reach one.
On the contrary, this has not always proved to be the case, so it is called a challenge.
Just like prime numbers are considered important in cryptography, such conjectures are considered important in software protection, especially obfuscation.
This is because it is difficult to identify the source of conjecture by using automated modern analysis technologies such as "symbolic execution" and "Tain Analysis".
In other words, humans can recognize protection techniques that include Collatz conjecture, but computers (Analysis Tools) can perform enormous amounts of computation without being aware, which can be interfered with analysis.
[Related Short Story - Dynamic Analysis & Static Analysis[2021/02/18]]
#Story #LootNiP #CollatzConjecture #Challenge #SoftwareProtection #Obfuscation #Prime #Cryptography