do I got any cryptography mutuals?
I'm puzzled about something with textbook RSA. Doesn't the message you encrypt need to be an integer that's coprime with N? So that it's in the multiplicative group? Seems like it would be a hassle to have a restriction on the messages
Conversation
bearing in mind that idk how commercial software actually resolves this problem, N is the product of two large primes so this isn’t very likely to be a problem, on the off chance it is you can reroll the primes or salt the message
1
2
do the products of two large primes not have that many numbers less than them that aren't coprime?
1
Replying to
about 1 / p of all numbers are divisible by p and about 1 / q of all numbers are divisible by q. so at most 1 / p + 1 / q of all numbers are divisible by either (it's exactly 1 / p + 1 / q - 1 / pq but that last term is very small)
the smallest keysizes i can find for RSA require N to be 1024 bits so p and q are around 512 bits. that means the probability the message is divisible by either is around 1 / 2^511 which is basically not worth considering
1
we are talking like, this is much less than the probability that a cosmic ray flips a bit in the machine while the algorithm is running
2