在公钥密码系统中跟踪原始私钥的可跟踪部分的方法

摘要

本发明的目的在于提出一种由Boneh和Franklin引入的叛逆者追踪算法的快速替代机制在公钥密码系统中跟踪私钥。本发明涉及在由一个公钥和l个相应的私钥组成的公钥密码系统中跟踪原始私钥的可跟踪部分的方法，一个私钥由可跟踪的2k个元素的数组形成，该数组形成由基点和缩放向量定义的具有参数的广义RS码的校正子，该方法包括如下步骤：获取欺诈私钥的可跟踪部分，在欺诈私钥的可跟踪部分应用Berlekamp-Massey算法，以获取错误定位器多项式的k个系数，在错误定位器多项式应用Chien的搜索算法，以获取错误定位器多项式的根；通过计算每个根的算术逆确定原始私钥可跟踪部分的基点，这些基点使得能够唯一地确定该私钥。

主权项

1.一种用于在由一个公钥和l个相应的私钥组成的公钥密码系统中跟踪原始私钥的可跟踪部分的方法，私钥由至少一个可跟踪的具有2k个元素的数组形成，该数组形成由基点和缩放向量定义的具有参数(l，l-2k)的广义RS码的校正子，所述方法包括如下步骤：获取欺诈私钥的可跟踪部分其中具有2k个元素的数组是属于至少两个原始私钥的具有2k个元素的数组的线性组合，使得该线性组合的系数之和等于1mod q，对欺诈私钥的可跟踪部分应用Berlekamp-Massey算法，以获取错误定位器多项式的k个系数，对错误定位器多项式应用Chien的搜索算法，以获取错误定位器多项式的根，通过计算每个根的算术逆确定原始私钥的可跟踪部分的基点，这些基点使得能够唯一地确定私钥身份。