如何计算rsa私钥的系数？

Question

我一直在试图制作一个特定的rsa私钥来解码消息 我有所有的值（p，q，d，n，e，e1，e2）但我无法找到系数，因为它说公式计算系数为(q^-1 mod p)。但是当我以p=17和q=11为例时，系数应该是14。但是当我用计算器计算时，coeffienct变为(0.0909090909)。 请给我一个方法来计算系数或给我以下对的系数。

asn1=SEQUENCE:rsa_key 

[rsa_key] 
version=INTEGER:0 

modulus=INTEGER:1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413 

pubExp=INTEGER:65537 

privExp=INTEGER:703813872109751212728960868893055483396831478279095442779477323396386489876250832944220079595968592852532432488202250497425262918616760886811596907743384527001944888359578241816763079495533278518938372814827410628647251148091159553 

p=INTEGER:878002287614711652531743087737814467999489 

q=INTEGER:511279233373417143396810270092798736308917 

e1=INTEGER:496787982169740923502343753899982600567297 

e2=INTEGER:80295249215525643071102598936432783036457 

coeff=INTEGER:? 

Answer 1

正如评论q指出^ -1模p是模反元素，你可以在此处详细了解：https://en.wikipedia.org/wiki/Modular_multiplicative_inverse

它使用扩展欧几里德算法进行计算，但是当模值像p原为17然后在这种情况下，很容易由下式来计算模逆：

q^-1 mod p = (q^(p-2)) mod p（仅当p是素数）

现在的答案是：（11^15）模17 = 4177248169415651 MOD 17 = 14

还要注意的是，当gcd(p, q) != 1

我想您所查询的系数是模块化逆不存在：457212035379609309760218035812085381175325

它可能不正确，则可能需要调查furthur。