In the book Cryptography and Network Security by Forouzan,in chapter 14, Fiat-Sh

Question

In the book Cryptography and Network Security by Forouzan,in chapter 14, Fiat-Shamir protocol, its mentioned that two large prime numbers p and q are chosen and kept secret. However n=p*q is made public. Then the claimant chooses s which lies between 1 and n-1(exclusive)........

Now here is the doubt: exclusive means he author wants to say that s belongs to the set (1,n-1) with no other restrictions on it. However, on internet, I have seen sites mentioning that s belongs to the set [1,n-1] but s must be co-prime with n. Now it is equivalent to say that s belongs to the set (1,n-1) since they have mentioned that s must be co-prime with n, so there is absolutely no way 1 and n-1 will be chosen. However the book doesn't mention anything like s must be co-prime with n. So I am confused with the rules applied in selecting s

Again r, the random number selected by claimant: the book mentions that it must be between 1 and n-1. So , I am confused whether its set is (1,n-1) or [1,n-1].

Explanation / Answer

It's the same situation as for RSA encryption. If you accidentally pick a bad s, i.e. one that's not coprime to N then the protocol fails. How likely is this to happen? If you hit a bad s, then you can find the factors of N, hence you can break the protocol - put another way, finding a bad s, whether deliberately or by accident is no easier than factoring N and breaking the whole thing anyway. And the whole reason that you're doing a protocol in an RSA group in the first place is because you believe that your N is big enough that it's infeasible to factor.

As for whether the boundaries 1 and N?1 are included, this really doesn't matter either - if your N is large enough then the chance of accidentally hitting the boundary when you sample uniformly from [1,N?1] is 2/N which is tiny.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.