NCJ Number
57876
Date Published
1978
Length
13 pages
Annotation
A SIMPLIFIED VERSION OF THE MERKLE-HELLMAN PUBLIC-KEY CRYPTOGRAPHIC SYSTEM IS BREAKABLE BUT THE FULL SYSTEM SEEMS TO RESIST ATTACK. THE SUCCESSFUL BREAK SUGGESTS WAYS TO IMPROVE SOFTWARE SECURITY.
Abstract
THE MERKEL-HELLMAN SOFTWARE USES A KNAPSACK SYSTEM, WHICH IS A VECTOR OF NATURAL NUMBERS. KNAPSACK PROBLEMS ARE OFTEN USED FOR CRYPTOGRAPHIC FUNCTIONS. THEY CAN BE USED IN PUBLIC-KEY CRYPTOGRAPHY BY LETTING EACH NETWORK MEMBER PUBLISH HIS KNAPSACK SYSTEM IN A NETWORK DIRECTORY. THIS SYSTEM IS USED TO CALCULATE A SUM WHICH WILL ENCODE A MESSAGE TO BE SENT OVER AN INSECURE COMMUNICATION CHANNEL. MERKLE AND HELLMAN USE A MODULUS (M) AND A MULTIPLIER (W) TO DISGUISE THE BASIC FORMULA AND MAKE THE ENCODING MORE DIFFICULT TO SOLVE. HOWEVER, ONCE AN OUTSIDER LEARNS THE VALUE OF M, THE SYSTEM IS HIGHLY VULNERABLE. MERKLE AND HELLMAN NOTE THAT A SAFER SYSTEM WOULD BE OBTAINED BY USING MODULAR MULTIPLICATIONS A NUMBER OF TIMES, RESULTING IN A NEW VALUE FOR M AT EACH ITERATION AND MAKING THE KNAPSACK SEQUENCE MORE COMPLEX. THIS STUDY FINDS THAT SUCH A TECHNIQUE INDEED MAKES THE SYSTEM MORE SECURE. THE CRYPTANALYTIC ATTACK WAS INEFFECTIVE EVEN WHEN ALL THE MODULUS NUMBERS AND ALL BUT THE LAST MULTIPLIERS WERE KNOWN. ANOTHER METHOD OF ELIMINATING THE POTENTIAL WEAKNESS USES STRUCTURE NUMBERS WHOSE LOW-ORDER PARTS ARE A SUPERINCREASING SEQUENCE AND WHOSE HIGH-ORDER PARTS ARE STRINGS OF RANDOM BITS. THIS PAPER IS A TECHNICAL DISCUSSION OF COMPUTER SECURITY CONTAINING MATHEMATICAL ILLUSTRATIONS AND A BRIEF BIBLIOGRAPHY. (GLR)