public—key密码系统破裂问题浅介

ELEMENTARY INTRODUCTION TO "CRACKING PROBLEM" OF A PKCS

任何一个公开密钥密码系统(pkcs)可能在非确定的多项式时间内破裂,那么,最低限度,在确定的多项式时间内pkcs则不应当破裂,证明意味着,已知系统在N≠NP时是安全的.简略地说:pkcs的“破裂问题”是一个明文信息M的计算问题,而M又是由未知当前脱密密钥的密码C编码的.典型的计算问题,转换成多项式时间的等值判定性问题,而计算问题的复杂性结构是结合判定问题的分类来度量的.从而,确立了密码复杂性转换成精确结构的论点.

Since any public-key Cryptosystem (PKCS) can be cracked nondeterminately in polynomial-time, minimally a PKCS should not be crackable determinately in polynomial-time. A proof that the given system is secure would imply p≠Np. in a word, the 'cracking problem' of a PKCS is the problem of computing the message M that is encoded by decryption key. Typical computational pro-blems are transformed into polynomial-time equivalent decision problems, and the complexity of the, original computational problem is measured by classifying the decision problem, in consequence,a certain issue is established that cryptocomplexity is transformed into the fine structure of NP.