Calculating RSA Signature at Message m=2 w/o Hash Function

  • MHB
  • Thread starter mathmari
  • Start date
In summary, the requirement that $ed \equiv 1 \pmod{\varphi(n)}$ is actually too strong. All you need is that: $$ed \equiv 1 \pmod{\mathrm{lcm}(p - 1, q - 1)}$$
  • #1
mathmari
Gold Member
MHB
5,049
7
Hey! :eek:

1. Construct a pair of private/public key RSA, where the prime numbers that we use are $p=11, q=13$.
2. Describe how we can calculate a RSA signature at the message $m=2$ without using a hash function.
3. Show that, given the above signature, we can calculate a valid signature at the message $m'=8$ without using the private key.

I have done the following:

1. $n=p \cdot q=11 \cdot 13$

$\phi(n)=(p-1)(q-1)=10 \cdot 12=120$

We choose a $e$ such that $(e,\phi(n))=1$. We take for example, $e=7$.

Then we calculate $d$ such that $ed \equiv 1 \pmod {\phi(n)}$. So, $d=13$.

The private key is $d=13$ and the public key is $(e, n)=(7, n)$.

2. The signature is $c=m^d \pmod {\phi(n)}$.

3. There is a $m_1$ such that $m=m'm_1$.

$c=m^d \pmod {\phi(n)} \Rightarrow c=m'^dm_1^d \pmod {\phi(n)} \\ \Rightarrow c(m_1^d)^{-1}=m'^d \pmod {\phi(n)} \Rightarrow cm_1^{-d}=m'^d \pmod {\phi(n)} \\ \Rightarrow ((cm_1^{-d})^{-e})^{-\frac{1}{e}}=m'^d \pmod {\phi(n)} \Rightarrow (c^{-e}m_1^{ed})^{-\frac{1}{e}}=m'^d \pmod {\phi(n)} \\ \Rightarrow (c^{-e}m_1)^{-\frac{1}{e}}=m'^d \pmod {\phi(n)}$

That means that the signature of the message $m'$ is $(c^{-e}m_1)^{-\frac{1}{e}}$.

Could you tell me if it is correct what I have done?? (Wondering)
 
Mathematics news on Phys.org
  • #2
mathmari said:
Hey! :eek:

1. Construct a pair of private/public key RSA, where the prime numbers that we use are $p=11, q=13$.
2. Describe how we can calculate a RSA signature at the message $m=2$ without using a hash function.
3. Show that, given the above signature, we can calculate a valid signature at the message $m'=8$ without using the private key.

I have done the following:

1. $n=p \cdot q=11 \cdot 13$

$\phi(n)=(p-1)(q-1)=10 \cdot 12=120$

We choose a $e$ such that $(e,\phi(n))=1$. We take for example, $e=7$.

Then we calculate $d$ such that $ed \equiv 1 \pmod {\phi(n)}$. So, $d=13$.

The private key is $d=13$ and the public key is $(e, n)=(7, n)$.

2. The signature is $c=m^d \pmod {\phi(n)}$.

3. There is a $m_1$ such that $m=m'm_1$.

$c=m^d \pmod {\phi(n)} \Rightarrow c=m'^dm_1^d \pmod {\phi(n)} \\ \Rightarrow c(m_1^d)^{-1}=m'^d \pmod {\phi(n)} \Rightarrow cm_1^{-d}=m'^d \pmod {\phi(n)} \\ \Rightarrow ((cm_1^{-d})^{-e})^{-\frac{1}{e}}=m'^d \pmod {\phi(n)} \Rightarrow (c^{-e}m_1^{ed})^{-\frac{1}{e}}=m'^d \pmod {\phi(n)} \\ \Rightarrow (c^{-e}m_1)^{-\frac{1}{e}}=m'^d \pmod {\phi(n)}$

That means that the signature of the message $m'$ is $(c^{-e}m_1)^{-\frac{1}{e}}$.

Could you tell me if it is correct what I have done?? (Wondering)

Hi mathmari,

The first part is correct. For the second part the signature is $c=m^d \pmod {n}=2^{13}\mbox{mod 141}$. For the third part you can use the homomorphic property of the RSA scheme. That is, $c^3=m^{3d}\pmod{n}$.
 
Last edited:
  • #3
Sudharaka said:
The first part is correct.

I calculated again $13 \cdot 7 \pmod {121} \equiv 91 \pmod {121}$. So, it is wrong, isn't it?? (Wondering)
Sudharaka said:
For the second part the signature is $c=m^d \pmod {n}=2^13\mbox{mod 141}$.

Oh, I wrote $c=m^d \pmod {\phi(n)}$ instead of $c=m^d \pmod {n}$. (Tmi)
Sudharaka said:
For the third part you can use the homomorphic property of the RSA scheme. That is, $c^3=m^{3d}\pmod{n}$.

So, is my idea completely wrong?? (Wondering)
 
  • #4
The requirement that $ed \equiv 1 \pmod{\varphi(n)}$ is actually too strong. All you need is that:
$$ed \equiv 1 \pmod{\mathrm{lcm}(p - 1, q - 1)}$$
But, yes, that is still wrong, as the lcm of 10 and 12 is 60, so 91 doesn't work out. A working $d$ is for example $d = 103$, or $d = 43$. Though $d = 13$ still "works" for a little more than half of all possible plaintext inputs, so the error isn't immediately visible. An example of failure, with $M = 2$:
$$2^7 \equiv 128 \pmod{143}$$
but
$$128^{13} \equiv 24 \not \equiv 2 \pmod{143}$$
 

Related to Calculating RSA Signature at Message m=2 w/o Hash Function

What is RSA Signature?

RSA Signature is a digital signature algorithm used in public-key cryptography. It allows for secure communication and authentication by using a public and private key pair to sign and verify messages.

Why is it important to calculate RSA Signature without a Hash Function?

Calculating RSA Signature without a Hash Function allows for a more efficient and faster process, as the data does not need to be hashed before being signed. This can be useful in applications where speed is crucial, such as in real-time communication.

What is the process for calculating RSA Signature at Message m=2 without a Hash Function?

The process involves using the private key to encrypt the message m=2 and then using the public key to decrypt it. This will result in a signature that can be verified by anyone with the public key.

What are the potential security risks of calculating RSA Signature without a Hash Function?

Without a Hash Function, there is a higher chance of collisions, where two different messages result in the same signature. This can potentially lead to security vulnerabilities, as the same signature could be used to verify different messages.

Are there any alternatives to calculating RSA Signature without a Hash Function?

Yes, there are alternatives such as using a Hash Function, which adds an extra layer of security by reducing the chances of collisions. Another option is to use a different signature algorithm, such as DSA or ECDSA, which also provide secure digital signatures.

Similar threads

Replies
4
Views
999
Replies
1
Views
932
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
716
Replies
1
Views
2K
  • General Math
Replies
1
Views
1K
  • General Math
Replies
3
Views
2K
  • General Math
Replies
7
Views
2K
Replies
4
Views
2K
Back
Top