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

  • Thread starter Thread starter mathmari
  • Start date Start date
AI Thread Summary
The discussion focuses on calculating an RSA signature for the message m=2 without using a hash function. The RSA keys are constructed using primes p=11 and q=13, resulting in a public key (e, n) and a private key d. The signature is initially calculated as c=m^d mod n, but a mistake is identified where the modulus should be n instead of φ(n). Additionally, the homomorphic property of RSA is highlighted, allowing for the calculation of a valid signature for a different message m'=8 without the private key. The requirement for ed to be congruent to 1 modulo φ(n) is clarified, emphasizing the need for it to be congruent to the least common multiple of (p-1) and (q-1).
mathmari
Gold Member
MHB
Messages
4,984
Reaction score
7
Hey! :o

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
mathmari said:
Hey! :o

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:
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)
 
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}$$
 
Insights auto threads is broken atm, so I'm manually creating these for new Insight articles. In Dirac’s Principles of Quantum Mechanics published in 1930 he introduced a “convenient notation” he referred to as a “delta function” which he treated as a continuum analog to the discrete Kronecker delta. The Kronecker delta is simply the indexed components of the identity operator in matrix algebra Source: https://www.physicsforums.com/insights/what-exactly-is-diracs-delta-function/ by...
Suppose ,instead of the usual x,y coordinate system with an I basis vector along the x -axis and a corresponding j basis vector along the y-axis we instead have a different pair of basis vectors ,call them e and f along their respective axes. I have seen that this is an important subject in maths My question is what physical applications does such a model apply to? I am asking here because I have devoted quite a lot of time in the past to understanding convectors and the dual...
Back
Top