# What is h in the improved solution of RSA algorithm?

I am trying to implement a proposed improved algorithm of RSA . Here the author has increased the number of exponents. However I am unable to understand what $h$ is in the Key generation step. Can someone tell me what $h$ is exactly?

The author's paper is : http://www.jacn.net/papers/47-N024.pdf I had originally posted this paper : http://iosrjournals.org/iosr-jece/papers/Vol9-Issue1/Version-5/H09154347.pdf

n = p x q
Ø(n) = (p-1)(q-1)
ϒ n, h = ph-p0 ph-p1…ph-ph-1 + qh-q0 qh- q1 … qh-qh-1
r such as 1 < r < n
and gcd r, Ø=1 and gcd r,ϒ=1 (r should be small integer)
e such as r.e = 1 mod Ø(n) and 1< e < Ø(n)
d such as d.e= 1mod ϒn and 1 < d < ϒn
Encryption Key = {e,n}… public key
Decryption Key = {r,d,n}… private key

-
Having had a quick look at that paper, I'm finding it hard to understand what their proposed improvement is. That is, I can't work out what benefits their scheme claims to give. Moreover, those variables aren't even used in their encryption/decryption algorithms. I'm far from convinced by this paper –  figlesquidge Apr 1 at 18:10
Ugh... I looked at the paper to try and fix the broken math formatting in the question, but it turns out to be like that in the paper too. :-( Honestly, most of the paper looks a lot like SCIgen output anyway. –  Ilmari Karonen Apr 1 at 18:59
Actually, these authors just copied the 2KGEA algorithm from their reference [3]: iasir.net/IJSWSpapers/IJSWS13-272.pdf - however, that paper doesn't answer any of the above questions. –  poncho Apr 1 at 19:57
@DrLecter Just adding that IOSR is actually an alleged predatory journal –  rath Apr 1 at 21:36
@figlesquidge I guess the majority of articles in that journal and the one referenced in ponchos comment will not have that many readers (you, Ilmari and the OP makes it already 3 ;) And as it seems for a good reason! –  DrLecter Apr 1 at 21:42

The authors of the paper might be able to tell you; I suspect no one else will.

You are having problems understanding the paper; a large part of the reason is that the paper isn't very well written; it introduces terminology (such as "ph") without ever defining it, and includes things that don't make any sense, such as the first line of their "Encryption Process": "If M=3, such that M$<$n ").

This might be an indication that they are not used to writing papers (along with their lack of fluency in English), or it might be an indication that they really don't know what they're talking about.

My best guess about their proposal (from making "corrections" in what they wrote, and in a way that's looks to be secure) would be:

• Select primes $p$ and $q$ and a small value $r$

• Compute $e = r^{-1} \bmod pq$ and $d = e^{-1} \bmod (p-1)(q-1)$ (there's no indication what to do if $e$ is not relatively prime to $(p-1)(q-1)$; perhaps pick a different $r$?)

• To encrypt a message $M$, compute $C = eM^e \bmod pq$

• To decrypt a message $C$, compute $M = (rC)^d \bmod pq$

This would work and also be secure (as it can be easily reduced to RSA); however it also begs the question "what advantages does it have over standard RSA?". After all, they use a large public exponent $e$ (remember, it's $r$ that is small); and so it would appear they're making the public operation more expensive; what benefit are they gaining for that expense (perhaps some tolerance to side channel attacks? If so, they would need to spell out the side-channel resistant implementation).

-
Can you explain how your solution can be reduced to RSA. –  user12817 Apr 2 at 19:09
Well, given a public key $(N,e)$ and plaintext/ciphertext pairs $(P,C)$, an attacker can replace it with an RSA key $(N,e)$ and plaintext/ciphertext pairs $(P,eC)$; any attack on this system would immediately imply an attack on the RSA system. We believe the RSA system to be secure (because, while $e$ was chosen so that $e^{-1}$ is small, there's no known weakness there), and hence this system is secure. –  poncho Apr 2 at 20:25

My previous answer was about the IOSR-JECE paper, since you posted the link to JACN paper, I went through that one as well.

That paper is considerably better written; it doesn't have any obvious meaningless sentences.

Unfortunately, the increased clarity makes it more obvious that their system is insecure as specified.

I'll abstract out the bits of the key generation process that show this (there are other steps they take; those other steps do not do anything to prevent this weakness):

1) Randomly and secretly choose two large primes: $p, q$ and compute $n = pq$

2) Compute $\phi(n) = (p-1)(q-1)$

Fairly standard

4) Select Random Integer: $r$ such as $1 < r < n$ and $gcd(r, \phi(n)) = 1$ ... ( $r$ should be a small integer).

Note that last comment: $r$ should be selected to be a small integer.

5) Compute $e$ such as $r \cdot e \equiv 1 \pmod{\phi(n)}$

So $e$ is the inverse of a small integer modulo $\phi(n)$

7) Public Key: $(e, n)$

Say what? We know how to factor $n$ given a public exponent that corresponds to a small (1/4th the size of the modulus) private exponent, and this is exactly what $e$ is; $e$ and $r$ will work as public/private exponents, and it matters not at all that's not how they use them. And, once we factor $n$, it's easy to decrypt messages with this scheme. Oddly enough, one of their references (number 11) is to a paper that describes this; one wonders if they actually read the paper.

There are a bunch of other things about this paper I could make fun of (such as their table 1, which gives time estimates of their RSA operation: they show an RSA key generation time a small multiple of the time taken by either the encryption or the decryption operation; and they show an encryption time larger than decryption -- haven't they heard that RSA can be used with small public exponents? I'll bet they ignore the CRT optimization in the decrypt direction as well), however there's nothing else in this paper that comes close to this severe security issue.

-

I have a lead about the origin and meaning of $h$, based on the abstract of an ITNG 2008 paper (which is reference [6] of the JACN paper):

In this paper, we propose an efficient RSA public key encryption scheme, which is improved version of original RSA scheme. The proposed RSA encryption scheme is based on linear group over the ring of integer mod a composite modulus $n$ which is the product of two distinct prime numbers. In the proposed scheme the original message and the encrypted message are $h\times h$ square matrices with entities in $\mathbb Z_n$ indicated via $l(h,\mathbb Z_n)$. Since the original RSA Scheme is a block cipher in which the original message and cipher message are integer in the interval $[0, n -1]$ for some integer modulus $n$. Therefore, in this paper, we generalize RSA encryption scheme in order to be implemented in the general linear group on the ring of integer mod $n$. Furthermore, the suggested encryption scheme has no restriction in encryption and decryption order and is claimed to be efficient, scalable and dynamic.

Note: blame me for any mistake introduced by the attempted $\TeX$ rendering.

Thus $h$ is the number of raw and columns of a square matrix of elements in $\mathbb Z_n$; that's corroborated by the JACN paper using " the general linear group of order $h$ ".

An hypothesis is that the various authors found $h$, and the impressive formulas in which it appears (increasingly garbled by the citation chain), to be decorative.

PS: I realize the question was " asked Apr 1 "; apologies for the late answer.

-