RSA question

[juan_gandhi]

WTF they do it now that encryption takes less time than decryption? Is not stuff encrypted usually once and decrypted many times? Or what's the reason? I mean the `e` in encryption key being low Hamming measure, instead of `d`. 

Comments

[malobukov]

Какая разница. RSA используется только чтоб подпись проверить. Сессионный ключ уже какой-нибудь Диффи-Хелман, дальше вообще симметричный шифр вроде AES или ChaCha20, где шифрование и дешифрование по времени одинаково.

[zuka]

и то уже ECDSA для подписей

[juan_gandhi]

А, вот как. Окей. Спасибо.

[archaicos]

А у меня сразу мысль «Чтоб никто не догадался!».
В смысле, народ уже начал придумывать приёмы угадывания ключей по всяким внешним признакам работы кода, по тому сколько времени что-то занимает, сколько памяти использует... И вот раньше все гении работали над тем чтобы всё ускорить, ведь так же лучше, да? А теперь иногда нужно и притормозить, т.к. оказывается, что иногда лучше медленно, да лучше.

[juan_gandhi]

Ну хм. Пять-десять бит ключа угадали, но это же только говорит нам, кто взаимно прост с (p-1)*(q-1). Что это дает в целом? Да ничего, наверно.

[sassa_nf]

There are simple timing attacks that help discover one bit at a time.

Eg "all [x == y for x,y in zip(expected, found)]"

Allows the observer find how many bytes were found correct by timing the execution. This simplifies search from intractable to tractable.

[ichthuss]

Low Hamming 'd' value would compromise security completely. 'd' should be random-looking. So the choice is between "low Hamming 'e', high Hamming 'd'" and "high Hamming value for both 'e' and 'd'".

[juan_gandhi]

Oh, right, I see. Everybody knows pq, so we just do exponentiation. I wonder if taking a root of a low Hamming degree is also hard. By just trying, like, 10k distinct 'e', or, as wiki says, "the most commonly chosen value for e is 2^16 + 1 = 65,537".

Anyway, I suddenly discovered lately that I forgot that part, about choosing `d` and `e` in RSA, and got confused.

Thanks!

BTW, do you want to fix the wiki article? https://en.wikipedia.org/wiki/RSA_(cryptosystem)

[sassa_nf]

That's what raising to d is, taking root of power e.

D is not chosen, it is computed as e^-1 mod (p-1)(q-1). Which makes m^d the root of degree e of m. No one can compute d, because they don't know (p-1)(q-1), because they can't factor pq.

Now, p and q are random, so d is also random, even if e isn't. E is small, so signature verification is faster. Because you can afford to choose e to make someone's life easier.

[sassa_nf]

E is public, so it doesn't matter what it is. You may just as well choose the one that makes life easy. So they choose some small number with two or three ones.

D is computed from E, so you can't choose what you get.