Super-Increasing Sequence Ⅹ=(X12Xx2…,xn) is super-increasing if (2, 3, 6, 13, 27, 52)is super-increasing
6 Super-Increasing Sequence • X = (x1 , x2 ,…, xn ) is super-increasing if − = 1 1 i j i j x x • (2,3,6,13,27,52 ) is super-increasing
Greedy Method Solve X=(2,3,6,13,27,52)ands=70 s>52?Yes=>b6=1,s1=70-52=18 18>27?No=>bs=0 18>13?Ye=>b4=1,S2=18-13=5 5>6?NO=>b3=0 5>3?Ye=>b2=1,s2=5-3=2 B=(1,10,1,0,1)
7 Greedy Method • Solve X = (2,3,6,13,27,52 ) and s = 70 • s > 52? Yes ==> b6 = 1, s1 = 70 - 52 = 18 • 18 > 27? No ==> b5 = 0 • 18 > 13? Yes ==> b4 = 1, s2 = 18 - 13 = 5 • 5 > 6? No ==> b3 = 0 • 5> 3? Yes ==> b2 = 1, s2 = 5 - 3 = 2 • b1= 1 • B = (1,1,0,1,0,1)
Greedy method To solve for i=1 down to 1 ·Ifs≥x S=S-X. b: =1 ·ElS b;=0
8 Greedy Method • To solve: – for i =1 down to 1 • If sxi – s = s-xi , bi = 1 • Else – bi = 0
Knapsack Based Public-Key Key generation Choose a super-increasing sequence ⅹ=( Choose randomly two numbers y and such that GCD(N,Y)=1, and Y>>x
9 Knapsack Based Public-Key • Key Generation: – Choose a super-increasing sequence X = (x1 , x2 ,…, xn ) – Choose randomly two numbers Y and such that GCD(N,Y) = 1, and = n j j Y x 1
Knapsack Based Public-Key Public Key: K=(kI, k, .,kn)where k,=x, N modY Private Key: XNY
10 Knapsack Based Public-Key • Public Key: – K = (k1 , k2 ,…, kn ) where ki = xi N mod Y • Private Key: – X, N, Y