METHOD FOR GENERATING SPARSE W-NAF KEY, METHOD FOR PROCESSING AND METHOD FOR ENCRYPTING THEREOF

摘要

PURPOSE: A method for generating a sparse w-NAF(Non Adjacent Form) key and a calculation method and an encryption method using the same are provided to improve coding speed by reducing an exponent power operation quantity or a scalar multiplication operation quantity. CONSTITUTION: A key generation unit selects any t number of groups from m-(w-1)*t number of groups(S410). The key generation unit replaces the selected t number of groups with a string which is made of one of positive odd numbers below 2w or w-1 number of 0s(S420). The key generation unit replaces the group which is not selected with 0(S430). A generated coefficient row is outputted by aτ-adic w-NAF key(S440). The scalar multiplication unit performs scalar multiplication based on theτ-adic w-NAF key which is generated through the key generation unit(S510-S560). [Reference numerals] (AA) Start; (BB) End; (S410) Selection of any t number of groups from the m-(w-1)(t) numbers of groups; (S420) Replacing of the selected t number of each group with a string which is formed by arranging the w-1 number of zeros and any one of integers whose absolute value is below qw/2 and which are aliquant by q; (S430) Replacing of non-selected groups with zero; (S440) Outputting of a coefficient generated through S410 and S430 steps to aτ-adic w-NAF key; (S510) Intermediate result value(Q)= [sign(initial coefficient which is not zero)]* |initial coefficient which is not zero|* P; (S520) Next coefficient = 0 ?; (S540) Q←τQ+[sign(next coefficient)]*|next coefficient|*P; (S550) Does the next coefficient exist?; (S560) Outputting of Q using scalar multiplication; (S610) Encoding