CODEWITHSUNDEEP
mathrsa
dummy
dummy

Reputation: 19

How to calculate the coefficient of a rsa private key?

I have been trying to make a specific rsa private key to decode a message I have all the value (p,q,d,n,e,e1,e2) but am unable to find the coefficient as it says the formula to calculate the coefficient is (q^-1 mod p). But when I take the example of p=17 and q=11 the coefficient should be 14. But when I calculate it with calculator the coeffienct comes to be (0.0909090909). Please give me a way to calculate the coefficent or give me the coefficient for the following pair.

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:?

Upvotes: 2

Views: 2757

Answers (1)

uSeemSurprised
uSeemSurprised

Reputation: 1834

As pointed out in the comments q^-1 mod p is modular multiplicative inverse, you can read more about here : https://en.wikipedia.org/wiki/Modular_multiplicative_inverse

It is calculated using Extended Euclidean algorithm, but when the modulo value is prime like p is 17 then in this case it is easy to calculate the modular inverse by the formulae :

q^-1 mod p = (q^(p-2)) mod p (only when p is prime)

Now the answer is : (11 ^ 15) mod 17 = 4177248169415651 mod 17 = 14

Also note that the modular inverse does not exist when gcd(p, q) != 1

I think the coefficient for your query is : 457212035379609309760218035812085381175325

It may not be correct, you might need to investigate furthur.

Upvotes: 1

Related Questions