US 7,080,255 B1 · Secret key generation method, encryption method, and cryptographic communications method and system

Abstract

A cryptographic communications method is provided which is based on ID-NIKS and is resilient to collusive attack. Centers (1) established in a plurality generate secret keys peculiar to entities (a, b) using division vectors wherein specifying information (ID information) for said entities is divided and personal secret random numbers set differently for each component in the division vectors. The centers (1) then distribute the secret keys to the entities. The entities generate common keys using components, contained in their own peculiar secret keys, that correspond to the division vectors of other entities. Each division vector is configured with codewords of an error correcting code.

Claims8

Dependent claims

A secret key generation method wherein:

secret keys peculiar to entities are generated by using division vectors indicating divided specifying information resulting from division of information specifying said entities into a plurality of blocks, and personal secret random numbers peculiar to said entities, set for each of said divided blocks;
said personal secret random numbers are set with different values for each component in said division vectors;
said secret keys are generated using said personal secret random numbers so set and said division vectors;
when number of divided blocks of said division vectors is taken as J, sizes of said division vectors as Mj (j=1, 2, . . . , J), and personal secret random number for entity e as βej(v) (v=0, 1, . . . , Mj−1), where β is a random number, all J divided blocks are grouped into K groups, with one or a plurality of blocks in each group;
and
said secret keys satisfy γeR1+γeR2+ . . . +γeRk=nλ(N)
where n is an integer, λ(.) is a Carmichael function, and N=PQ (where P and Q are prime),
where:
RK is a partial set of universal set U having, as members, natural numbers up to J,
Rp∩Rq is an empty set for any p and q, and R1 U R2
U . . . U RK is said universal set U;
and
γeRk is a constant value obtained by calculating personal secret random numbers and correction terms in each component in division vector corresponding to Sk.

10 more elements

A cryptographic communications system wherein:

encrypting processing for encrypting plaintext that is information to be sent into ciphertext and decrypting processing for decrypting ciphertext sent back into original plaintext are performed reciprocally between a plurality of entities;
having:
a plurality of centers that generate secret keys peculiar to said entities, following the formulas given below, using divided specifying information resulting from division of information specifying said entities into a plurality of blocks, using row vectors corresponding to said divided specifying information for said entities, each of said row vectors being selected from a symmetrical matrix peculiar to each block, and the secret keys to the entities;
and
a plurality of entities each of which generates common keys employed in said encryption processing and said decryption processing, following the formulas given below, using components, contained in own secret key thereof, sent from said centers, that correspond to divided specifying information of entities to be communicated with, wherein computation formulas for generating said secret keys are as follows,
{right arrow over (sR,i(j))}≡αi({right arrow over (hR,i(j))}+{right arrow over (γR,i(j))})(mod λ(N))
{right arrow over (sL,i(j))}≡βi({right arrow over (hL,i(j))}+{right arrow over (γL,i(j))})(mod λ(N))
Secret keys gaipbiqcir numbering (T+1)(T+2)/2
where p+q+r=T,
ai, bi, and ci satisfy following relationships
ai·αi≡1(mod λ(N))
bi·βi≡1(mod λ(N))
∑
j
=
1
J
⁢
⁢
γ
i
(
j
)
+
c
i
=
λ
⁡
(
N
)
where
vector SR,i(j) and vector SL,i(j) are two types of secret key corresponding to j'th divided specifying information for entity i (j=2, 3, . . . , J);
vector hR,i(j), vector hL,i(j) are key division vector of entity i, vector hR,i(j)+vector hL,i(j)=vector hi(j);
vector hi(j) is a vector obtained by extracting one row from a matrix H(j) corresponding to j'th divided specifying information for entity i;
H(j) is a symmetrical 2Mj×2Mj matrix formed of random numbers;
Mj is size of j'th divided specifying information for entity i;
J is number of block divisions in specifying information for entity i;
αi, βi are personal secret random numbers for entity i;
where gcd (αi, λ(N))=1,
gcd (βi, λ(N))=1, and
λ(·) is Carmichael function;
N is an integer;
γi(j), ci are personal secret random numbers for entity i
where γi(1)+γi(2)+ . . . +γi(J)+ci=λ(N)
vector γR,i(j), vector γL,i(j) are random number division vectors of entity i, vector γR,im(j)+vector γL,im(j)=γi(j) vector 1 for entity m (where vector 1=(1, 1, . . . , 1);
g is an integer mutually prime with N;
and
T is degree of exponent portion, and wherein,
K
im
≡
⁢
∏
p
+
q
+
r
=
T
⁢
⁢
(
a
i
p
g
⁢
b
i
q
⁢
c
i
r
)
S
R
,
im
p
⁢
S
L
,
im
q
⁢
T
!
p
!
⁢
q
!
⁢
r
!
≡
⁢
∏
p
+
q
+
r
=
T
⁢
g
⁢
T
!
p
!
⁢
q
!
⁢
r
!
⁢
X
R
,
im
p
⁢
X
L
,
im
q
⁢
c
i
r
≡
⁢
g
⁢
∑
p
+
q
+
r
=
T
⁢
⁢
T
!
p
!
⁢
q
!
⁢
r
!
⁢
X
R
,
im
p
⁢
X
L
,
im
q
⁢
c
i
r
≡
⁢
(
X
R
,
im
+
X
L
,
im
+
c
i
)
T
g
≡
⁢
{
∑
j
=
1
J
⁢
⁢
(
h
R
,
im
j
(
j
)
+
γ
R
,
im
j
(
j
)
+
h
L
,
im
j
(
j
)
+
γ
L
,
im
j
(
j
)
)
+
c
i
}
T
g
≡
⁢
g
⁢
(
∑
j
=
1
J
⁢
⁢
h
i
j
⁢
m
j
(
j
)
+
λ
⁡
(
N
)
)
T
≡
⁢
(
∑
j
=
1
J
⁢
⁢
h
i
j
⁢
m
j
(
j
)
)
T
g
≡
⁢
K
mi
⁡
(
mod
⁢
N
)
where
SR,im is a sum on the integer ring of components SR,imj(j) corresponding to the divided specifying information for entity m, extracted from the secret key vector SR,i(j) for entity i, expressed as given below;
SL,im is a sum on the integer ring of components SL,imj(j) corresponding to the divided specifying information for entity m, extracted from the secret key vector SL,i(j) for entity i, expressed as given below;
and
Kim is a common key generated by one entity i for another entity m, and wherein,
S
R
,
im
=
⁢
∑
j
=
1
J
⁢
⁢
s
R
,
im
j
(
j
)
=
⁢
α
i
⁢
X
R
,
im
where . . .
X
R
,
i
⁢
m
=
⁢
∑
j
=
1
J
⁢
⁢
h
R
,
i
⁢
m
j
(
j
)
+
∑
j
=
1
J
⁢
⁢
γ
R
,
i
⁢
m
j
(
j
)
S
L
,
i
⁢
m
=
⁢
∑
j
=
1
J
⁢
⁢
s
L
,
i
⁢
m
j
j
=
⁢
β
i
⁢
X
L
,
i
⁢
m
where . . .
X
L
,
i
⁢
m
=
∑
j
=
1
J
⁢
⁢
h
L
,
i
⁢
m
j
(
j
)
+
∑
j
=
1
J
⁢
⁢
γ
L
,
i
⁢
m
j
(
j
)

465 more elements

A computer-readable medium for recording a program designed to cause a computer, at an entity end, to generate a common key used in encryption processing from plaintext to ciphertext and in decryption processing from ciphertext to plaintext in a cryptographic communications system, wherein

said program comprises:
first program code means for causing said computer to select components corresponding to divided specifying information for another entity to be communicated with from a secret key peculiar to said entity produced according to formulas below for each divided specifying information resulting from division of specifying information for said entity into a plurality of blocks;
and
second program code means for causing said computer to generate said common key according to formulas below using said selected components, wherein
{right arrow over (sR,i(j))}≡αi({right arrow over (hR,i(j))}+{right arrow over (γR,i(j))})(mod λ(N))
{right arrow over (sL,i(j))}≡βi({right arrow over (hL,i(j))}+{right arrow over (γL,i(j))})(mod λ(N))
Secret keys gaipbiqcir numbering (T+1)(T+2)/2
where p+q+r=T,
ai, bi, and ci satisfy following relationships
ai·αi≡1(mod λ(N))
bi·βi≡1(mod λ(N))
∑
j
=
1
J
⁢
⁢
γ
i
(
j
)
+
c
i
=
λ
⁡
(
N
)
where
vector SR,i(j) and vector SL,i(j) are two types of secret key corresponding to j'th divided specifying information for entity i (j=2, 3, . . . , J);
vector hR,i(j), vector hL,i(j) are key division vector of entity i, vector hR,i(j)+vector hL,i(j)=vector hi(j);
vector hi(j) is a vector obtained by extracting one row from a matrix H(j) corresponding to j'th divided specifying information for entity i;
H(j) is a symmetrical 2Mj×2Mj matrix formed of random numbers;
Mj is size of j'th divided specifying information for entity i;
J is number of block divisions in specifying information for entity i;
αi, βi are personal secret random numbers for entity i
where gcd (αi, λ(N))=1,
gcd (βi, λ(N))=1, and
λ(·) is Carmichael function;
N is an integer;
γi(j), ci are personal secret random numbers for entity i
where γi(1)+γi(2)+ . . . +γi(J)+ci=λ(N)
vector γR,i(j), vector γL,i(j) are random number division vectors of entity i, vector γR,im(j)+vector γL,im(j)=γi(j) vector 1 for entity m (where vector 1=(1, 1, . . . , 1);
g is an integer mutually prime with N;
and
T is degree of exponent portion, and wherein,
K
im
≡
⁢
∏
p
+
q
+
r
=
T
⁢
⁢
(
a
i
p
g
⁢
b
i
q
⁢
c
i
r
)
S
R
,
im
p
⁢
S
L
,
im
q
⁢
T
!
p
!
⁢
q
!
⁢
r
!
≡
⁢
∏
p
+
q
+
r
=
T
⁢
g
⁢
T
!
p
!
⁢
q
!
⁢
r
!
⁢
X
R
,
im
p
⁢
X
L
,
im
q
⁢
c
i
r
≡
⁢
g
⁢
∑
p
+
q
+
r
=
T
⁢
⁢
T
!
p
!
⁢
q
!
⁢
r
!
⁢
X
R
,
im
p
⁢
X
L
,
im
q
⁢
c
i
r
≡
⁢
(
X
R
,
im
+
X
L
,
im
+
c
i
)
T
g
≡
⁢
{
∑
j
=
1
J
⁢
⁢
(
h
R
,
im
j
(
j
)
+
γ
R
,
im
j
(
j
)
+
h
L
,
im
j
(
j
)
+
γ
L
,
im
j
(
j
)
)
+
c
i
}
T
g
≡
⁢
g
⁢
(
∑
j
=
1
J
⁢
⁢
h
i
j
⁢
m
j
(
j
)
+
λ
⁡
(
N
)
)
T
≡
⁢
(
∑
j
=
1
J
⁢
⁢
h
i
j
⁢
m
j
(
j
)
)
T
g
≡
⁢
K
mi
⁡
(
mod
⁢
N
)
where
SR,im is a sum on the integer ring of components SR,imj(j) corresponding to the divided specifying information for entity m, extracted from the secret key vector SR,i(j) for entity i, expressed as given below;
SL,im is a sum on the integer ring of components SL,imj(j) corresponding to the divided specifying information for entity m, extracted from the secret key vector SL,i(j) for entity i, expressed as given below;
and
Kim is a common key generated by one entity i for another entity m, and wherein
S
R
,
i
⁢
⁢
m
=
∑
j
=
1
J
⁢
⁢
s
R
,
i
⁢
⁢
m
j
(
j
)
=
α
i
⁢
X
R
,
i
⁢
⁢
m
where . . .
X
R
,
i
⁢
m
=
⁢
∑
j
=
1
J
⁢
⁢
h
R
,
i
⁢
m
j
(
j
)
+
∑
j
=
1
J
⁢
⁢
γ
R
,
i
⁢
m
j
(
j
)
S
L
,
i
⁢
m
=
⁢
∑
j
=
1
J
⁢
⁢
s
L
,
i
⁢
m
j
(
j
)
=
⁢
β
i
⁢
X
L
,
i
⁢
m
where . . .
X
L
,
i
⁢
m
=
∑
j
=
1
J
⁢
⁢
h
L
,
i
⁢
m
j
(
j
)
+
∑
j
=
1
J
⁢
⁢
γ
L
,
i
⁢
m
j
(
j
)

473 more elements

A computer data signal embodied in a carrier wave for transmitting a program comprising:

first program code means for causing said computer to select components corresponding to divided specifying information for another entity to be communicated with from secret keys peculiar to said entity produced according to formulas below for each divided specifying information of said entity resulting from division of specifying information for said entity into a plurality of blocks;
and
second program code means for causing said computer to generate a common key according to formulas below using said selected components, wherein
{right arrow over (sR,i(j))}≡αi({right arrow over (hR,i(j))}+{right arrow over (γR,i(j))})(mod λ(N))
{right arrow over (sL,i(j))}≡βi({right arrow over (hL,i(j))}+{right arrow over (γL,i(j))})(mod λ(N))
Secret keys gaipbiqcir numbering (T+1)(T+2)/2
where p+q+r=T
ai, bi, and ci satisfy following relationships
ai·αi≡1(mod λ(N))
bi·βi≡1(mod λ(N))
∑
j
=
1
J
⁢
⁢
γ
i
⁢
(
j
)
+
c
i
=
λ
⁡
(
N
)
where
vector SR,i(j) and vector SL,i(j) are two types of secret key corresponding to j'th divided specifying information for entity i (j=2, 3, . . . , J);
vector hR,i(j), vector hL,i(j) are key division vector of entity i, vector hR,i(j)+vector hL,i(j)=vector hi(j);
vector hi(j) is a vector obtained by extracting one row from a matrix H(j) corresponding to j'th divided specifying information for entity i;
H(j) is a symmetrical 2Mj×2Mj matrix formed of random numbers;
Mj is size of j'th divided specifying information for entity i;
J is number of block divisions in specifying information for entity i;
αi, βi are personal secret random numbers for entity i
where gcd (αi, λ(N))=1,
gcd (βi, λ(N))=1, and
λ(·) is Carmichael function;
N is an integer;
γi(j), ci are personal secret random numbers for entity i
where γi(1)+γi(2)+ . . . αγi(J)+ci=λ(N)
vector γR,i(j), vector γL,i(j) are random number division vectors of entity i, vector γR,im(j)+vector γL,im(j)=γi(j) vector 1 for entity m (where vector 1=(1, 1, . . . , 1);
g is an integer mutually prime with N;
and
T is degree of exponent portion, and wherein
K
i
⁢
⁢
m
≡
⁢
∏
p
+
q
+
r
=
T
⁢
⁢
(
g
a
i
p
⁢
b
i
q
⁢
c
i
r
)
S
R
,
im
p
⁢
S
L
,
im
q
⁢
T
!
p
!
⁢
q
!
⁢
r
!
≡
⁢
∏
p
+
q
+
r
=
T
⁢
g
T
!
p
!
⁢
q
!
⁢
r
!
⁢
X
R
,
im
p
⁢
X
L
,
im
q
⁢
c
i
r
≡
⁢
g
⁢
∑
p
+
q
+
r
=
T
⁢
⁢
T
!
p
!
⁢
q
!
⁢
r
!
⁢
X
R
,
im
p
⁢
X
L
,
im
q
⁢
c
i
r
≡
⁢
g
⁡
(
X
R
,
im
+
X
L
,
im
+
c
i
)
T
≡
⁢
g
⁢
{
∑
j
=
1
J
⁢
⁢
(
h
R
,
im
j
(
j
)
+
γ
R
,
im
j
(
j
)
+
h
L
,
im
j
(
j
)
+
γ
L
,
im
j
(
j
)
)
+
c
i
}
T
≡
⁢
g
⁡
(
∑
j
=
1
J
⁢
⁢
h
i
j
⁢
m
j
(
j
)
+
λ
⁡
(
N
)
)
T
≡
⁢
g
⁡
(
∑
j
=
1
J
⁢
⁢
h
i
j
⁢
m
j
(
j
)
)
T
≡
⁢
K
m
⁢
⁢
i
⁡
(
mod
⁢
⁢
N
)
where
SR,im is a sum on the integer ring of components SR,imj(j) corresponding to the divided specifying information for entity m, extracted from the secret key vector SR,i(j) for entity i, expressed as given below;
SL,im is a sum on the integer ring of components SL,imj(j) corresponding to the divided specifying information for entity m, extracted from the secret key vector SL,i(j) for entity i, expressed as given below;
and
Kim is a common key generated by one entity i for another entity m, and wherein,
S
R
,
i
⁢
⁢
m
=
∑
j
=
1
J
⁢
⁢
s
R
,
i
⁢
⁢
m
j
(
j
)
=
α
i
⁢
X
R
,
i
⁢
⁢
m
where . . .
X
R
,
i
⁢
m
=
⁢
∑
j
=
1
J
⁢
⁢
h
R
,
i
⁢
m
j
(
j
)
+
∑
j
=
1
J
⁢
⁢
γ
R
,
i
⁢
m
j
(
j
)
S
L
,
i
⁢
m
=
⁢
∑
j
=
1
J
⁢
⁢
s
L
,
i
⁢
m
j
(
j
)
=
⁢
β
i
⁢
X
L
,
i
⁢
m
where . . .
X
L
,
i
⁢
m
=
∑
j
=
1
J
⁢
⁢
h
L
,
i
⁢
m
j
(
j
)
+
∑
j
=
1
J
⁢
⁢
γ
L
,
i
⁢
m
j
(
j
)

482 more elements

An encryption method wherein:

specifying information of an entity is divided into a plurality of blocks of divided specifying information, a plurality of row vectors corresponding to said plurality of blocks of divided specifying information are prepared, with each of said row vectors being selected from a symmetrical matrix peculiar to each block;
secret keys peculiar to said entity are generated using said plurality of row vectors;
plaintext is encrypted to ciphertext using a common key generated using components contained in said secret keys, said components corresponding to said plurality of blocks of divided specifying information of another entity that is destination of said ciphertext;
and
computation formulas for generating said secret keys are as follows,
{right arrow over (sR,i(j))}≡αi({right arrow over (hR,i(j))}+{right arrow over (γR,i(j))})(mod λ(N))
{right arrow over (sL,i(j))}≡βi({right arrow over (hL,i(j))}+{right arrow over (γL,i(j))})(mod λ(N))
Secret keys gaipbiqcir numbering (T+1)(T+2)/2
where p+q+r=T,
ai, bi, and ci satisfy following relationships
ai·αi≡1(mod λ(N))
bi·βi≡1(mod λ(N))
∑
j
=
1
J
⁢
⁢
γ
i
⁢
(
j
)
+
c
i
=
λ
⁡
(
N
)
where
vector SR,i(j) and vector SL,i(j) are two types of secret key corresponding to j'th divided specifying information for entity i (j=1, 2, . . . , J);
vector hR,i(j), vector hL,i(j) are key division vector of entity i,
vector hR,i(j)+vector hL,i(j)=vector hi(j);
vector hi(j) is a vector obtained by extracting one row from a matrix H(j), corresponding to j'th divided specifying information for entity i;
H(j) is a symmetrical 2Mj×2Mj matrix formed of random numbers;
Mj is size of j'th divided specifying information for entity i;
J is number of block divisions in specifying information for entity i;
αi, βi are personal secret random numbers for entity i
where gcd (αi, λ(N))=1,
gcd (βi, λ(N))=1, and
λ(·) is Carmichael function;
N is an integer;
γi(j), ci are personal secret random numbers for entity i
where γi(1)+γi(2)+ . . . +γi(J)+ci=λ(N)
vector γR,i(j), vector γL,i(j) are random number division vectors of entity i, vector γR,im(j)+vector γL,im(j)=γi(j) vector 1 for entity m (where vector 1=(1, 1, . . . , 1));
g is an integer mutually prime with N;
T is degree of exponent portion;
and
wherein computation formulas for generating said secret keys are as follows:
K
i
⁢
⁢
m
≡
⁢
∏
p
+
q
+
r
=
T
⁢
⁢
(
g
a
i
p
⁢
b
i
q
⁢
c
i
r
)
S
R
,
im
p
⁢
S
L
,
im
q
⁢
T
!
p
!
⁢
q
!
⁢
r
!
≡
⁢
∏
p
+
q
+
r
=
T
⁢
g
T
!
p
!
⁢
q
!
⁢
r
!
⁢
X
R
,
im
p
⁢
X
L
,
im
q
⁢
c
i
r
≡
⁢
g
⁢
∑
p
+
q
+
r
=
T
⁢
⁢
T
!
p
!
⁢
q
!
⁢
r
!
⁢
X
R
,
im
p
⁢
X
L
,
im
q
⁢
c
i
r
≡
⁢
g
⁡
(
X
R
,
im
+
X
L
,
im
+
c
i
)
T
≡
⁢
g
⁢
{
∑
j
=
1
J
⁢
⁢
(
h
R
,
im
j
(
j
)
+
γ
R
,
im
j
(
j
)
+
h
L
,
im
j
(
j
)
+
γ
L
,
im
j
(
j
)
)
+
c
i
}
T
≡
⁢
g
⁡
(
∑
j
=
1
J
⁢
⁢
h
i
j
⁢
m
j
(
j
)
+
λ
⁡
(
N
)
)
T
≡
⁢
g
⁡
(
∑
j
=
1
J
⁢
⁢
h
i
j
⁢
m
j
(
j
)
)
T
≡
⁢
K
m
⁢
⁢
i
⁡
(
mod
⁢
⁢
N
)
where
SR,im is a sum on the integer ring of components SR,imj(j) corresponding to the divided specifying information for entity m, extracted from the secret key vector SR,i(j) for entity i;
this sum is expressed as given below;
SL,im is a sum on the integer ling of components SL,imj(j) corresponding to the divided specifying information for entity m, extracted from the secret key vector SL,i(j) for entity I;
this sum is expressed as given below;
and
Kim is a common key generated by one entity i for another entity m, and wherein,
S
R
,
i
⁢
⁢
m
=
∑
j
=
1
J
⁢
⁢
s
R
,
i
⁢
⁢
m
j
(
j
)
=
α
i
⁢
X
R
,
i
⁢
⁢
m
where . . .
X
R
,
i
⁢
m
=
⁢
∑
j
=
1
J
⁢
⁢
h
R
,
i
⁢
m
j
(
j
)
+
∑
j
=
1
J
⁢
⁢
γ
R
,
i
⁢
m
j
(
j
)
S
L
,
i
⁢
m
=
⁢
∑
j
=
1
J
⁢
⁢
s
L
,
i
⁢
m
j
(
j
)
=
⁢
β
i
⁢
X
L
,
i
⁢
m
where . . .
X
L
,
i
⁢
m
=
∑
j
=
1
J
⁢
⁢
h
L
,
i
⁢
m
j
(
j
)
+
∑
j
=
1
J
⁢
⁢
γ
L
,
i
⁢
m
j
(
j
)

488 more elements

An encryption method wherein:

specifying information of an entity is divided into a plurality of blocks of divided specifying information, a plurality of row vectors corresponding to said plurality of blocks of divided specifying information are prepared, with each of said row vectors being selected from a symmetrical matrix peculiar to each block;
secret keys peculiar to said entity are generated using said plurality of row vectors;
plaintext is encrypted to ciphertext using a common key generated using components contained in said secret keys, said components corresponding to said plurality of blocks of divided specifying information of another entity that is destination of said ciphertext;
and
computation formulas for generating said secret keys are as follows,
{right arrow over (sR,i(j))}≡αi({right arrow over (hR,i(j))}+{right arrow over (γR,i(j))})(mod λ(N))
{right arrow over (sL,i(j))}≡βi({right arrow over (hL,i(j))}+{right arrow over (γL,i(j))})(mod λ(N))
Secret keys gaipbiqcir numbering (T+1)(T+2)/2
where p+q+r=T
ai, bi, and ci satisfy following relationships
ai·αi≡1(mod λ(N))
bi·βi≡1(mod λ(N))
∑
j
=
1
J
⁢
⁢
γ
i
⁢
(
j
)
+
c
i
=
λ
⁡
(
N
)
where
vector SR,i(j) and vector SL,i(j) are two types of secret key corresponding to j'th divided specifying information for entity i (j=1, 2, . . . , J);
vector hR,i(j), vector hL,i(j) are key division vector of entity i,
vector hR,i(j)+vector hL,i(j)=vector hi(j);
vector hi(j) is a vector obtained by extracting one row from a matrix H(j), corresponding to j'th divided specifying information for entity i;
H(j) is a symmetrical 2Mj×2Mj matrix formed of random numbers;
Mj is size of j'th divided specifying information for entity i;
J is number of block divisions in specifying information for entity i;
αi, βi are personal secret random numbers for entity i
where gcd (αi, λ(N))=1, gcd (βi, λ(N))=1, and
λ(·) is Carmichael function;
N is an integer;
γi(j), ci are personal secret random numbers for entity i where γi(1)+γi(2)+ . . . +γi(J)+ci=λ(N)
vector γR,i(j), vector γL,i(j) are random number division vectors of entity i, vector γR,im(j)+vector γL,im(j)=γi(j) vector 1 for entity m (where vector 1=(1, 1, . . . , 1));
g is an integer mutually prime with N;
T is degree of exponent portion;
wherein either said N is such that N=PQ (where P and Q are prime), or said N is prime, and said g is a maximum generating element having modulo N;
and wherein computation formulas for generating said secret keys are as follows:
K
i
⁢
⁢
m
≡
⁢
∏
p
+
q
+
r
=
T
⁢
⁢
(
g
a
i
p
⁢
b
i
q
⁢
c
i
r
)
S
R
,
im
p
⁢
S
L
,
im
q
⁢
T
!
p
!
⁢
q
!
⁢
r
!
≡
⁢
∏
p
+
q
+
r
=
T
⁢
g
T
!
p
!
⁢
q
!
⁢
r
!
⁢
X
R
,
im
p
⁢
X
L
,
im
q
⁢
c
i
r
≡
⁢
g
⁢
∑
p
+
q
+
r
=
T
⁢
⁢
T
!
p
!
⁢
q
!
⁢
r
!
⁢
X
R
,
im
p
⁢
X
L
,
im
q
⁢
c
i
r
≡
⁢
g
⁡
(
X
R
,
im
+
X
L
,
im
+
c
i
)
T
≡
⁢
g
⁢
{
∑
j
=
1
J
⁢
⁢
(
h
R
,
im
j
(
j
)
+
γ
R
,
im
j
(
j
)
+
h
L
,
im
j
(
j
)
+
γ
L
,
im
j
(
j
)
)
+
c
i
}
T
≡
⁢
g
⁡
(
∑
j
=
1
J
⁢
⁢
h
i
j
⁢
m
j
(
j
)
+
λ
⁡
(
N
)
)
T
≡
⁢
g
⁡
(
∑
j
=
1
J
⁢
⁢
h
i
j
⁢
m
j
(
j
)
)
T
≡
⁢
K
m
⁢
⁢
i
⁡
(
mod
⁢
⁢
N
)
where SR,im is a sum on the integer ring of components SR,im(j) corresponding to the divided specifying information for entity m, extracted from the secret key vector SR,i(j) for entity i, expressed as given below;
SL,im is a sum on the integer ring of components SL,imj(j) corresponding to the divided specifying information for entity m, extracted from the secret key vector SL,i(j) for entity i, expressed as given below;
and
Kim is a common key generated by one entity i for another entity m, and wherein
S
R
,
i
⁢
⁢
m
=
∑
j
=
1
J
⁢
⁢
s
R
,
i
⁢
⁢
m
j
(
j
)
=
α
i
⁢
X
R
,
i
⁢
⁢
m
where . . .
X
R
,
i
⁢
m
=
⁢
∑
j
=
1
J
⁢
⁢
h
R
,
i
⁢
m
j
(
j
)
+
∑
j
=
1
J
⁢
⁢
γ
R
,
i
⁢
m
j
(
j
)
S
L
,
i
⁢
m
=
⁢
∑
j
=
1
J
⁢
⁢
s
L
,
i
⁢
m
j
(
j
)
=
⁢
β
i
⁢
X
L
,
i
⁢
m
where . . .
X
L
,
i
⁢
m
=
∑
j
=
1
J
⁢
⁢
h
L
,
i
⁢
m
j
(
j
)
+
∑
j
=
1
J
⁢
⁢
γ
L
,
i
⁢
m
j
(
j
)

483 more elements

A cryptographic communications method wherein:

specifying information of one entity is divided into a first plurality of blocks of divided specifying information, a first plurality of row vectors are provided for the first plurality of blocks of divided specifying information respectively, each of said row vectors being selected from a symmetrical matrix peculiar to each block;
specifying information of another entity is divided into a second plurality of blocks of divided specifying information, a second plurality of row vectors are provided for the second plurality of blocks of divided specifying information respectively, each of said row vectors being selected from a symmetrical matrix peculiar to each block;
a plurality of centers are deployed such that said plurality of centers generate first secret keys for said first plurality of row vectors respectively using said first plurality of row vectors, the first secret keys being peculiar to said one entity, and send the first secret keys to said one entity, and generate second secret keys for said second plurality of row vectors respectively using said second plurality of row vectors, the second secret keys being peculiar to said another entity, and send the second secret keys to said another entity;
said one entity encrypts plaintext to ciphertext using a first common key divided from the first secret keys, said first common key being generated using components contained in the first secret keys, said components corresponding to said second plurality of blocks of divided specifying information, and sends the ciphertext to said another entity;
said another entity decrypts said ciphertext so sent using a second common key identical to said first common key, said second common key being derived from the second secret keys, said second common key being generated using components contained in said second secret keys, said components corresponding to said first plurality of divided specifying information of said one entity;
and
computation formulas for generating said first and second secret keys are as follows:
{right arrow over (sR,i(j))}≡αi({right arrow over (hR,i(j))}+{right arrow over (γR,i(j))})(mod λ(N))
{right arrow over (sL,i(j))}≡βi({right arrow over (hL,i(j))}+{right arrow over (γL,i(j))})(mod λ(N))
Secret keys gaipbiqcir numbering (T+1)(T+2)/2
where p+q+r=T,
ai, bi, and ci satisfy following relationships
ai·αi≡1(mod λ(N))
bi·βi≡1(mod λ(N))
∑
j
=
1
J
⁢
⁢
γ
i
⁢
(
j
)
+
c
i
=
λ
⁡
(
N
)
where
vector SR,i(j) and vector SL,i(j) are two types of secret key corresponding to j'th divided specifying information for entity i G=2, 3, . . . , J);
vector hR,i(j), vector hL,i(j) are key division vector of entity i, vector hR,i(j)+vector hL,i(j)=vector hi(j);
vector hi(j) is a vector obtained by extracting one row from a matrix H(j) corresponding to j'th divided specifying information for entity i;
H(j) is a symmetrical 2Mj×2Mj matrix formed of random numbers;
Mj is size of j'th divided specifying information for entity i;
J is number of block divisions in specifying information for entity i;
αi, βi are personal secret random numbers for entity i
where gcd (αi, λ(N))=1,
gcd (βi, λ(N))=1, and
λ(·) is Carmichael function;
N is an integer;
γi(j), ci are personal secret random numbers for entity i
where γi(1)+γi(2)+ . . . +γi(J)+ci=λ(N)
vector γR,i(j), vector γL,i(j) are random number division vectors of entity i, vector γR,im(j)+vector γL,im(j)=γi(j) vector 1 for entity m (where vector 1=(1, 1, . . . , 1);
g is an integer mutually prime with N;
T is degree of exponent portion;
and
wherein computation formulas for generating said secret keys peculiar to entities are as follows:
K
i
⁢
⁢
m
≡
⁢
∏
p
+
q
+
r
=
T
⁢
⁢
(
g
a
i
p
⁢
b
i
q
⁢
c
i
r
)
S
R
,
im
p
⁢
S
L
,
im
q
⁢
T
!
p
!
⁢
q
!
⁢
r
!
≡
⁢
∏
p
+
q
+
r
=
T
⁢
g
T
!
p
!
⁢
q
!
⁢
r
!
⁢
X
R
,
im
p
⁢
X
L
,
im
q
⁢
c
i
r
≡
⁢
g
⁢
∑
p
+
q
+
r
=
T
⁢
⁢
T
!
p
!
⁢
q
!
⁢
r
!
⁢
X
R
,
im
p
⁢
X
L
,
im
q
⁢
c
i
r
≡
⁢
g
⁡
(
X
R
,
im
+
X
L
,
im
+
c
i
)
T
≡
⁢
g
⁢
{
∑
j
=
1
J
⁢
⁢
(
h
R
,
im
j
(
j
)
+
γ
R
,
im
j
(
j
)
+
h
L
,
im
j
(
j
)
+
γ
L
,
im
j
(
j
)
)
+
c
i
}
T
≡
⁢
g
⁡
(
∑
j
=
1
J
⁢
⁢
h
i
j
⁢
m
j
(
j
)
+
λ
⁡
(
N
)
)
T
≡
⁢
g
⁡
(
∑
j
=
1
J
⁢
⁢
h
i
j
⁢
m
j
(
j
)
)
T
≡
⁢
K
m
⁢
⁢
i
⁡
(
mod
⁢
⁢
N
)
where
SR,im is a sum on the integer ring of components SR,imj(j) corresponding to the divided specifying information for entity
m, extracted from the secret key vector SR,i(j) for entity i, expressed as given below;
SL,im is a sum on the integer ring of components SL,imj(j) corresponding to the divided specifying information for entity m, extracted from the secret key vector SL,i(j) for entity i, expressed as given below;
and
Kim is a common key generated by one entity i for another entity m, and wherein
S
R
,
i
⁢
⁢
m
=
∑
j
=
1
J
⁢
⁢
s
R
,
i
⁢
⁢
m
j
(
j
)
=
α
i
⁢
X
R
,
i
⁢
⁢
m
where . . .
X
R
,
i
⁢
m
=
⁢
∑
j
=
1
J
⁢
⁢
h
R
,
i
⁢
m
j
(
j
)
+
∑
j
=
1
J
⁢
⁢
γ
R
,
i
⁢
m
j
(
j
)
S
L
,
i
⁢
m
=
⁢
∑
j
=
1
J
⁢
⁢
s
L
,
i
⁢
m
j
(
j
)
=
⁢
β
i
⁢
X
L
,
i
⁢
m
where . . .
X
L
,
i
⁢
m
=
∑
j
=
1
J
⁢
⁢
h
L
,
i
⁢
m
j
(
j
)
+
∑
j
=
1
J
⁢
⁢
γ
L
,
i
⁢
m
j
(
j
)

488 more elements

A cryptographic communications method wherein:

specifying information of one entity is divided into a first plurality of blocks of divided specifying information, a first plurality of row vectors are provided for the first plurality of blocks of divided specifying information respectively, each of said row vectors being selected from a symmetrical matrix peculiar to each block;
specifying information of another entity is divided into a second plurality of blocks of divided specifying information, a second plurality of row vectors are provided for the second plurality of blocks of divided specifying information respectively, each of said row vectors being selected from a symmetrical matrix peculiar to each block;
a plurality of centers are deployed such that said plurality of centers generate first secret keys for said first plurality of row vectors respectively using said first plurality of row vectors, the first secret keys being peculiar to said one entity, and send the first secret keys to said one entity, and generate second secret keys for said second plurality of row vectors respectively using said second plurality of row vectors, the second secret keys being peculiar to said another entity, and send the second secret keys to said another entity;
said one entity encrypts plaintext to ciphertext using a first common key divided from the first secret keys, said first common key being generated using components contained in the first secret keys, said components corresponding to said second plurality of blocks of divided specifying information, and sends the ciphertext to said another entity;
said another entity decrypts said ciphertext so sent using a second common key identical to said first common key, said second common key being derived from the second secret keys, said second common key being generated using components contained in said second secret keys, said components corresponding to said first plurality of divided specifying information of said one entity;
and
computation formulas for generating said first and second secret keys are as follows:
{right arrow over (sR,i(j))}≡αi({right arrow over (hR,i(j))}+{right arrow over (γR,i(j))})(mod λ(N))
{right arrow over (sL,i(j))}≡βi({right arrow over (hL,i(j))}+{right arrow over (γL,i(j))})(mod λ(N))
Secret keys gaipbiqcir numbering (T+1)(T+2)/2
where p+q+r=T,
ai, bi, and ci satisfy following relationships
ai·αi≡1(mod λ(N))
bi·αi≡1(mod λ(N))
∑
j
=
1
J
⁢
⁢
γ
i
⁢
(
j
)
+
c
i
=
λ
⁡
(
N
)
where
vector SR,i(j) and vector SL,i(j) are two types of secret key corresponding to j'th divided specifying information for entity i G=2, 3, . . . , J);
vector hR,i(j), vector hL,i(j) are key division vector of entity i, vector hR,i(j)+vector hL,i(j)=vector hi(j);
vector hi(j) is a vector obtained by extracting one row from a matrix H(j) corresponding to j'th divided specifying information for entity i;
H(j) is a symmetrical 2Mj×2Mj matrix formed of random numbers;
Mj is size of j'th divided specifying information for entity i;
J is number of block divisions in specifying information for entity i;
αi, βi are personal secret random numbers for entity i
where gcd (αi, λ(N))=1,
gcd (βi, λ(N))=1, and
λ(·) is Carmichael function;
N is an integer;
γi(j), ci are personal secret random numbers for entity i
where γi(1)+γi(2)+ . . . +γi(J)+ci=λ(N)
vector γR,i(j), vector γL,i(j) are random number division vectors of entity i, vector γR,im(j)+vector γL,im(j)=γi(j) vector 1 for entity m (where vector 1=(1, 1, . . . , 1);
g is an integer mutually prime with N;
T is degree of exponent portion;
wherein either said N is such that N=PQ (where P and Q are prime), or said N is prime, and said g is a maximum generating element having modulo N;
and
wherein computation formulas for generating said secret keys peculiar to entities are as follows:
K
i
⁢
⁢
m
≡
⁢
∏
p
+
q
+
r
=
T
⁢
⁢
(
g
a
i
p
⁢
b
i
q
⁢
c
i
r
)
S
R
,
im
p
⁢
S
L
,
im
q
⁢
T
!
p
!
⁢
q
!
⁢
r
!
≡
⁢
∏
p
+
q
+
r
=
T
⁢
g
T
!
p
!
⁢
q
!
⁢
r
!
⁢
X
R
,
im
p
⁢
X
L
,
im
q
⁢
c
i
r
≡
⁢
g
⁢
∑
p
+
q
+
r
=
T
⁢
⁢
T
!
p
!
⁢
q
!
⁢
r
!
⁢
X
R
,
im
p
⁢
X
L
,
im
q
⁢
c
i
r
≡
⁢
g
⁡
(
X
R
,
im
+
X
L
,
im
+
c
i
)
T
≡
⁢
g
⁢
{
∑
j
=
1
J
⁢
⁢
(
h
R
,
im
j
(
j
)
+
γ
R
,
im
j
(
j
)
+
h
L
,
im
j
(
j
)
+
γ
L
,
im
j
(
j
)
)
+
c
i
}
T
≡
⁢
g
⁡
(
∑
j
=
1
J
⁢
⁢
h
i
j
⁢
m
j
(
j
)
+
λ
⁡
(
N
)
)
T
≡
⁢
g
⁡
(
∑
j
=
1
J
⁢
⁢
h
i
j
⁢
m
j
(
j
)
)
T
≡
⁢
K
m
⁢
⁢
i
⁡
(
mod
⁢
⁢
N
)
where
SR,im is a sum on the integer ring of components SR,imj(j) corresponding to the divided specifying information for entity m, extracted from the secret key vector SR,i(j) for entity i, expressed as given below;
SL,im is a sum on the integer ring of components SL,imj(j) corresponding to the divided specifying information for entity m, extracted from the secret key vector SL,i(j) for entity i, expressed as given below;
and
Kim is a common key generated by one entity i for another entity m,
where
S
R
,
i
⁢
m
=
⁢
∑
j
=
1
J
⁢
⁢
s
R
,
i
⁢
m
j
(
j
)
=
⁢
α
i
⁢
X
R
,
i
⁢
m
where . . .
X
R
,
i
⁢
m
=
⁢
∑
j
=
1
J
⁢
⁢
h
R
,
i
⁢
m
j
(
j
)
+
∑
j
=
1
J
⁢
⁢
γ
R
,
i
⁢
m
j
(
j
)
S
L
,
i
⁢
m
=
⁢
∑
j
=
1
J
⁢
⁢
s
L
,
i
⁢
m
j
j
=
⁢
β
i
⁢
X
L
,
i
⁢
m
where . . .
X
L
,
i
⁢
m
=
∑
j
=
1
J
⁢
⁢
h
L
,
i
⁢
m
j
(
j
)
+
∑
j
=
1
J
⁢
⁢
γ
L
,
i
⁢
m
j
(
j
)

486 more elements

Dependencies are inferred from the claim text.

Secret key generation method, encryption method, and cryptographic communications method and system

Life of this patent

Secret key generation method, encryption method, and cryptographic communications method and system

Life of this patent

Abstract

Claims8