Transcript 双曲線暗号について

What is the Hyperbolic Curve
Cryptosystem?
This is a presentation of Hyperbolic Curve
Cryptosystem for the beginners.
originally filed at Feb.02,2007
first revision at Aug.14,2007
second revision at Nov.26,2007
Kimito Horie
What is the Hyperbolic Curve
Cryptosystem?
1. The Hyperbolic Curve Cryptosystem（ＨＣＣ）
is a
general system of a key generation method, a key generation
apparatus, a decoding method, a decoding apparatus, a signature
verification method and a signature verification apparatus using a
quadratic hyperbolic curve group.
２、 Quadratic Hyperbolic Curve Group(QHCG)
is a
finite commutative group consists of integers on a quadratic
hyperbolic curve over a finite ring. That curve is made of the
denominator of second order function of x and the numerator of
linear function of x ,such that
f(x)=(x-b)/(x2+cx-a).
> A kind of a cyclic group.
Every element of QHCG is cyclic, which
mean after the finite numbers of a group addictive operation that element
returns to itself.
>
For example,an element P will be an unit element O after k-operations, that
is
kP=O, which means P+P+P...+P=O.
An example of QHCG.
y=(x-b)/(x2+cx-a)
x,a,b,c,y∈Z/pZ,
(x2+cx-a) is a non quadratic
residue under modulo p.
I would explain this equation and the conditions next.
(1) What is the group ?
(2) What is the residual ring Z/pZ ?
(3) What is the non quadratic residue ?
(4) Why QHCG needs the condition of the non quadratic residue?
(5) What is the quadratic hyperbolic curve ?
What is the group ?
The group is a pair of a set G and a operator * defined in G, (G,*).
>This is an idea of ancestors for classifying the set from others by an
algebraic structure, and must satisfy next four conditions;
(1) Group operation is defined between any two elements in G, and
the result must be also in G. For example,
if G={ a,b,,,} and think a*b by a group operation *, then a*b must be in G.
>This means if there is any resultant element which do not belong to G,
then G is not a group (=the set G must be closed for a group
operation).
>If there is any pair of a set G, in which the operation can not define,
then you must delete such elements to make a group.
(2) Satisfy the associative law.
This means if G={ a,b,c,,, } and group operator is *, then
a*(b*c)=(a*b)*c must be satisfied.
>The group must have minimum symmetries for the group operation, the
changing an order of the operations must generate the same result.
>If you willfully define your own operation in G, it would not satisfy the
associative law.
What is the group ? (continued)
(3) Have an Unit element.
Any element a∈G and an unit element e∈G, it must be a*e=a.
> If the group have no unit element, then any element could not
represent itself. And could not reach to itself, after any operations.
(4) Every element in G is reversible. That means Any element a
∈G have an element such b∈G, like a*b=e.
>If there is an element which have no reverse element, then it could
not define itself by the operation.
Elliptic Curve Group and Hyperbolic Curve Group satisfy above 4
conditions. The group operation defined there is addictive one, such
that in ECG;
What is the group ? (continued)
Addictive operation in HCG is defined, such that;
The crossing point between the line and the curve of order 3 make in
whole the function of order 3, in which it has 3 roots.
>You can fix x4 concretely from the relations between the root and the
curve parameters. This means the addictive operation ‘+’ is defined,
such that Ｐ(x1)＋Ｑ(x2)＝Ｒ(x4) on HCG elements.
>This twice crossing operations make the group operation to be
determinative and constructive.
What is the residual ring Z/pZ ?
The ring is a pair of a set G and operators defined on G, * for
multiplication and + for addition, that is (G,*,+). And it also satisfy
an associative law and commutative law for each operators.
>At least the ring must have two operators for Add. and Multi.
The residual ring Z/pZ has ‘the operation of residues’ which occurs
from a division by modulo p.
If a,b∈Z/pZ, then a+b∈Z/pZ and a*b∈Z/pZ .
And satisfy a distributive law, like
if a,b,c∈Z/pZ, then a*(b+c)=a*b+a*c.
>QHCG is defined on the residual ring Z/pZ, so you can use both
operators of Add. and Multi. on the group operation to calculate the
crossing point x4. Thus QHCG have double structure in relation to
the operators, one is on Z/pZ and another is on QHCG as a group
operation.
>But you might not confuse these operators, for example Ｐ(x)＋Ｑ(y)
and x+y could be distinguished by there elements.
What is the non quadratic residue ?
We try to calculate the square of a integer on the residual ring Z/pZ.
x= 1 2 3 4 5 6 7 8 9 10
x2= 1 4 9 5 3 3 5 9 4 1 (mod 11)
So almost half numbers disappear after the square operation.
The number which appear after the square operation can represent
x2=b, and the value b is called ‘a quadratic residue’.
The number which disappear after the square operation can not
represent x2=b, x2-b≠0, and the value b is called ‘a non quadratic
residue’. Above example show such b=2,6,7,8,10.
Well, the famous Fermat’s little theorem states for any value b, (b,p)=1,
b(p-1)=1 (mod p) is satisfied.
And (p-1) is even, then it should be b(p-1)/2=1 or b(p-1)/2=-1 (mod p).
Non quadratic residue ? (continued)
If b(p-1)/2=-1 then there exist no x for which x2=b, because if x2=b then
that equation leads to xp-1=-1 by the power of (p-1)/2. This result is
contradiction itself by Fermat’s little theorem. So b(p-1)/2=-1 shows the
value b is a non quadratic residue, and b(p-1)/2=+1 shows the value b is a
quadratic residue. This is called Euler’s criterion, which is very
convenient for confirming only by calculations whether a value b is a
quadratic residue, or not.
For example, 2(11-1)/2=32=-1 (mod11) means b=2 is a non quadratic
residue.
Why QHCG has a condition of being a
non quadratic residue for (x2+cx-a) ?
>This reason is to maintain a group structure, the result of a group
operation should be also an element of that group, and the group
operation must be defined all over that group, as explained later.
>This condition is thought to be very loose, because the rank of
QHCG is constant in any changes of curve parameters.
What is the Quadratic Hyperbolic Curve ?
QHCG defined on the residual ring Z/pZ has a curve, such that
y=(x-b)/(x2+cx-a) (mod p).
This function has the denominator, by which taking the inverse element
under modulo p, and it is not the division likely on a real number.
This means the function we take out is not the geometrical curve itself.
But both of the inverse operation and the division on a real number
have same operation, on which the common factor is eliminable
both of the numerator and the denominator.
So, I use this style of the division as a simple expression of inverse
operation under modulo p, and as the number theory function which
do not have a relation with Geometry, though the name of ‘curve
parameter’ is used.
Please do not concern with a shape of the curve. The curve
parameters are the coefficients of the function of x, and you can
understand this group from the relations between the roots and the
coefficients as used on Algebra.
Numerical Example for QHCG.
When the parameter a=7,b=2,c=0 under modulo p=11,
the QHGC defined on the residual ring is expressed as the function
y=(x-2)/(x2-7) (mod 11)
under the condition (x2-7) is a non quadratic residue.
You can calculate the points (x,y) which satisfy above equation,
as the element (5,2), (6,10), (9,5), (8,3), (3,6), and an unit element (2,0).
>If you select the start point(=base point) P=(5,2), then the mP is
calculated by the group operation, and the result become the points
ordered above.
They are 2P=(6,10), 3P= (9,5), 4P=(8,3), 5P=(3,6), 6P=(2,0), and 7P=P,
then cycles again, that mean the rank k=6.
On this case, the rank means the elementary numbers of that group,
and it is coincident with the maximum period of the group.
Numerical Example for HCG(continued)
There exist 11 points on the residual ring Z/11Z, and the
all have possibilities of taking the point on that function.
But the rest of the above(5 points) are eliminated for a
reason of not satisfying the condition that (x2-7) is a non
quadratic residue.
So, the element P(x,y) with the value x which satisfy
(x2-7)(p-1)/2=1 is not a member of QHGC.
In addition, when the rank k=6, then the sub-group is
generated with the rank of it’s dividers, like d=6,3,2,1.
If you select the start point P=(6,10), then the mP is
calculated by the group operation, and the result become
2P=(8,3), 3P=(2,0), thus the rank of this sub-group is d=3.
Features of HCC
Hyperbolic Curve Cryptosystem(HCC) have a base on the problem of
Discrete Logarithm.
>A cryptosystem usually use the difficulties of mathematical problem which
could not be solved.
(1) What is Discrete Logarithm problem?
In a group of multiplication, this is a problem on which the difficulties to get
x in the relation with y=gx (mod p), after y and g are known. This is a
problem to get x= loggy (mod p) on Z.
For example, if g=2,p=11and y=8, then it is easy to get x=3, because 3=log28
as you know, but if y=7 can you seek x= log27 (mod 11) directly? To
calculate orderly we get
x= 1 2 3 4 5 6 7 8
2x= 2 4 8 5 10 9 7 3 (mod 11)
then we know as x=7, that it.
But if we extend the numbers very large like 100 bits, this calculation is
enormously heavy. Can you get the solution for the x, which satisfy
48589x=39951(mod 97177)? >The answer is x=12345.
But please make an attention that this is only the explanation for treating a
group of multiplication, not for an addictive group on the curve.
Features of HCC(continued)
（2）HCC and Discrete Logarithm problem
Discrete Logarithm problem on HCC is the difficulties to get the secret
key α by the group operation, after knowing the working key Y and
the base point G with the relation Ｙ＝αＧ.
>This relation is made of multiple group operations, not of the
multiplication itself. If you calculate Y step by step with α times
group operations, then the enormous calculation time will be
consumed, when the treated numbers are very large.
>If you know the value α first, then you can use a very faster method,
high speed index calculations on power. This is a method, for which
at first expand α like α=a0+a121+a222+a323+,
then calculate 2nＧ by the group addition of 2n-1Ｇ with itself.
This calculation is easy as compared with the direct calculation, and
N/ (2ｌｏｇ２Ｎ) times faster, and can work well even on the calculation
of an inverse element of the residual ring Z/pZ.
>Total amount of calculations diminish to 1/1028 when the key of
cryptosystem has 100 bits.
But the burden of calculations on the inverse element of QHCG is still
heavy with this method, and it might be still unclear to realize the
streaming cryptosystem.
Features of HCC(continued 2)
(3) The rank of the QHCG is constant in any changes of curve
parameters.
ｋ＝（ｐー１） ／２＋１
A rank said to be the numbers of its element on the finite commutative
group. In terms of the rank of Elliptic Curve Group, Hasse’s
theorem(1934) proved the rank k of Elliptic Curve Group(ECG) must be
p+1-2√p≦k ≦ p+1+2√p
, that show us this rank is almost around p.
But we should remind us the fact this rank depends on the parameters of
the ECG. So, practical method of using ECG is to give the random
numbers to the parameters, and after giving the trial prime k which
satisfy above inequalities, confirm whether the relations kP=O is
satisfied, or not.
Said the rank used to be a prime to make a practical cryptosystem in any
case. When the group has a prime rank, every element can be the base
point G except an unit element, that mean if the group has a
composite number rank, you must select the base point which has the
maximum rank k, and this way is not easy.
As described later, the rank of QHCG is a composite number when you
select the modulo n to be composite, though the rank is still constant.
Features of HCC(continued 3)
(4) Selection of the prime rank of QHCG
It is desirable to select the rank of QHCG being a prime as same
with ECG.
So, you must select a pair of primes like,
q=(p-1)/2+1
which mean the so called ‘Germann primes’ must have enough
densities among Z. If the modulo p, and parameters are very
large, that densities will diminish. But you can find many pairs of
Germann primes on the prime table. For example, p=541,q=271 is
OK.
This may be the first case for Germann primes to get meanings on
Technology.
To compare with ECG, QHCG has a pretty fine merit having the
features of the constant rank which can specify the usable group
before the design, and also the group parameters can select
under the easy restrictions.
Features of HCC(continued 4)
On any QHCG system you can make many QHCGs with same
constant rank, that is impossible or very difficult on the design
of ECG.
Because of the constant rank, the group structure and
operation are almost same with each other in the same rank
QHCGs, as the same systems work on the same hardware.
So, you can change the parameters and even the secret key
on the cryptosystem which have plural QHCG system with the
same rank inside.
>You can make an easy and secure cryptosystem by changing
the secret key, parameters, or operations time by time with
not so large bits cryptosystem, that is the parameter
changeable type cryptosystem, or operation changeable type
cryptosystem.
Construction of HC-Elgamal Cryptsystem
It is said the Elgamal cryptosystem is general and available for almost any
finite commutative group, and the QHCG is same.
That public key cryptosystem is constructed as this;
(1) The base point G, the working key Y(=αG), and the curve parameters are
selected as the public key, and using random number ｒ(1<r<k) with
a message m, Ｃ１＝ｒＧ、Ｃ２＝ｒＹ、and Ｃ３＝ｍ（Ｃ２）ｘ are calculated,
provided that （Ｃ２）ｘ means x axis value of C2.
>The purpose of using random number ｒ is to hide the secret key α and C2.
Remember the calculation of Y should be done by the addictive group
operation on QHCG.
(2)Now the public key is constructed as (G,Y,parameters,p), and the secret
message is (C1,C3). So, the term C1 contains the random number used, and
the term C3 contains the message included.
>If you use the public key, then you can make the encrypted message
by yourself. But as you do not know the secret key, you can not confirm
the encrypted message is correctly encrypted, or not.
Construction of HC-Elgamal (continued)
(3) The person who knows the secret key of this message m can
derive m itself from the relation ｍ＝Ｃ３／ （αＣ１）ｘ by the
inverse element calculation on Z/pZ.
>Network offenders could not calculate C2 and message m,
because they do not know the random number r and the secret
key α.
If they try to get the random number r from the relation Ｃ１＝ｒＧ,
the total amount time of that calculation is very enormous because
of the discrete logarithm problem, and they could not find it within
an effective time.
But you need the modulo p and others to be very large, more than
100 bits numbers to ensure the securities.
The features of HCC vs. EHC
Base of
cryptosystem
Rank
Construction
Public key
cryptosystem
Signature
verification
Streaming
EHC
HCC
descrete Logarithm
descrete Logarithm
Changeable with
parameters
uneasy
Constant
easy
OK
OK
OK
OK
uneasy
not uneasy
I think there are no differences between EHC and HCC, in terms of
the judgment of the prime , total amount of calculations time, and
difficulties of solving the discrete logarithmic problem. But HCC can
increase the securities much more by the parameter changeable type
cryptosystem or operation changeable type cryptosystem..
Streaming cryptosystem on HCC is not easy because of an heavy
calculation time, but said ‘method of an after calculations’ for an inverse
element may be effective. In reality, high speed streaming is not easy
now.
Circumstaces of HCC
(1)Patent applications were already filed, but not disclosed yet.
> Waiting for the public disclosure from JPO and USPO.
(2)HCC is not appealed yet, except this WEB.
Not advertised, and not evaluated in public yet.
>But I think HCC is comparable with ECC, though I have no evidence with it.
Sometimes a cryptosystem would be loose its value, when the solution
has found. There is also some possibility to meet such situation for HCC.
(3)In spite of such situation, I believe, HCC will become the next generation
cryptosystem after RSA, which is still alive and popular. But RSA is
taking off its merit of simplicity, using large bits numbers to secure its
system.
HCC can design and construct easily and one can understand with a primary
number theory, that is the reason why I believe it will spread over
>I would like to proceed HCC to be an international standard.
>And HCC will become the tools for the extension of Mathematics and
Cryptosystem.
Thank you for reading,
Kimito Horie in Tokyo.