1

Consider the following hash function based on RSA. $M_i < n$. The hash value of a message consisting of two blocks is calculated by

$H(M) = H(M_1,M_2) = ((M_1^e\ mod\ n)\ XOR\ M_2)^e mod\ n$

Q1.Does this hash function can produce fixed output size?

My answer: Because any output is limited to the modulus(n), the hash function can produce fixed output size?(I think of it for a long time, but I still wonder about it)

Q2.Is the hash function easy to calculate?

My answer: Because the hash function just contain encryption and XOR operations, it is easy to calculate.(Is it right or completed?)

Xiaoyu-2019
  • 11
  • Welcome to MS£. Please use Mathjax/Latex for the formulae in your question. See this excellent tutorial. – almagest Oct 01 '19 at 14:17
  • Thanks you very much! – Xiaoyu-2019 Oct 01 '19 at 14:22
  • This seems to be about RSA Digital Signatures or alternatively about the first crude attempts to use RSA for encryption. The problems were nothing to do with speed/efficiency, but were about insecurity. I agree with your answers to Q1, Q2. For Q3, the answer today would be Y provided the block size is not too long (eg 64 or 128 bits fine). Because "is it efficient?" usually means "is it efficient enough to be feasible with today's computers?" – almagest Oct 01 '19 at 14:28
  • Sorry, I had edited it. – Xiaoyu-2019 Oct 01 '19 at 14:30

1 Answers1

0

It's a weird chaining mode of RSA, and the output can be seen as a string of the length equal to that of $n$, as we output a number modulo $n$. So yes to Q1, provided you output a fully padded string.

It's not easy to calculate, but that's a bit subjective. The cost is two RSA operations essentially (xor is very cheap on computers) and those are relatively expensive compared to real hash functions (like SHA256 or SHA3 and many others). It's easily doable, but relatively expensive.

It's very insecure though.

Henno Brandsma
  • 242,131