배낭 암호 (Knapsack cryptosystem)
배낭 암호 배낭의 무게가 N일때 a0~ak까지 물건의 무게의 합이 정확히 N일때를 찾아야함 오늘날의 표준 기준으로 보면 안전하지 않지만, 오늘날 사용하는 공개키 암호 시스템을 만드는 토대가 되었다. 정의 a=[a1,a2, ,,, ,ak], x=[x1,x2, ,,, ,xk], xi=0 또는 1 s=knapsackSum(a,x)=x1a1+x2a2+ ,,, + xkak이다. 주어진 a와 x로부터 s를 계산하는것은 아주 쉽다. 하지만 s와 a가 주어졌을때 x를 구하는 것은 어렵다. 초증가 순서짝 → ai ≥ a1+ a2+… +ai-1 인 경우를 말한다. 즉, a1을 제외한 각 원소가 그 이전의 모든 원소의 합보다 크거나 같을 때를 말한다. 예제 a = [17, 25, 46, 94, 201, 400] 이고 s =..
2022. 11. 11.
