Document

三項暗号KM(3)-PKCの提案
～公開鍵サイズが非常に小さいチャレンジ問題提出～
平成１７年１１月１４日
大阪学院大学
笠原正雄
大阪電気通信大学村上恭通
内容
積和型暗号について，より安全性の高い構成法と
して三項暗号を提案する．
 公開鍵サイズが 347 ビット，暗号文サイズ183
ビットの解読が容易と思われる挑戦問題を “Very
Simple Challenge” として提出する．
 “Simple Challenges” として公開鍵サイズ 500,
700 ビット程度の比較的解読が容易と思われる
問題を提出し，解読を求める．
 “Challenges” として公開鍵サイズ 1000 ビット程
度の問題を提出し，解読を求める．

Challenge Problems (e=2)
Class
Problem
Message
Size
Ciphertext
Size
Public-key
Size
Problem3
140
183
347
Problem4
210
273
517
Problem6
412
533
1011
Very Simple
Challenge
I
Simple
Challenges
II
Challenges
III
単位 [bit]
Challenge Problems
Very Simple
Challenge
Simple
Challenges
e Message Size Ciphertext Size
Public-key Size
Problem 3
2
140
183
347
Problem 1
3
200
271
496
Problem 2
3
280
381
706
Problem 4
2
210
273
517
Problem 5
3
398
544
1021
Problem 6
2
412
533
1011
Challenges
単位 [bit]
List of Symbols
| I | : size of integer I (in bits);
 α, β, γ, σ: random positive integers;
 N : modulus of a random positive integer;
 e : public system prarameter;
 d : inverse element of e (mod λ(γ));
 λ(γ) : Carmichael functin of γ;
 Spk : size of public key;

Generation of
Secret Keys and Public Keys
Algorithm I
Step 1: Generate (k+1)-bit random integers, α, β
and (l+1)-bit random integer γ,
such that gcd(α,β)=gcd(β,γ)=gcd(γ,α)=1.
Step 2: Generate a public key a3
for which the relation gcd(a3, N)=1 holds.
Step 3: Given a3, σ and N, the following u is obtained:
u = a3 σ-1 (mod N).
Step 4: Given α,β,γ and N,
the public keys a1, a2 are obtained as follows:
a1 = uβγ (mod N),
a2 = uαγ (mod N).
Secret Keys and Public Keys

Secret Keys:
α, β,γ, σ, N

Public Keys:
a1, a2, a3
Encryption

Letting the messages,
m1 and m2 be k-bit positive integers and
m3 be an l-bit positive integer.

The ciphertext C∈Z is obtained as follows:
C = a1 m1 + a2 m2 + a3 m3e
Decryption
Algorithm II
Let the intermediate message M be
M = βγm1 + αγm2 + σ m3e.
Step 1: The intermediate message M is obtained as follows:
M = u-1 C (mod N).
Step 2: The message m3 can be obtained as follows:
m3 = (σ-1 M)d (mod γ), where d = e-1 (mod λ(γ)).
Step 3: The messages m1 and m2 can be decoded as follows:
M’ = (M-σm3e)／γ,
m1 = β-1 M’ (mod α),
m2 = α-1 M’ (mod β).
Design Conditions
Condition 1 (Decryption)
M<N
 Condition 2 (Size of the terms of M)
| βγm1 | = | αγm2 | = |σm3e |
 Condition 3 (High density over 1)
| C | < | m1 | + | m2 | + e | m3 |
 Condition 4 (Size of the terms of C)
| a1 m1 | = | a2 m2 | = | a3 m3e|

Rate and Density

Rate R:
size of message (in bits)
R=
size of ciphertext (in bits)

Density D:
size of pertinently enlarged message (in bits)
D=
size of ciphertext (in bits)
Parameter Settings
From Condition 3, D > 1 must be required for being
secure against LDA.
From Eqs.(21) and (22), the following relation holds:
k+4
2k
< l < e-1
e-1
From Eq.(23), we recommend the following l:
3k
l ≒ 2(e-1)
We see that e is required to take on a small value
in order to obtain a large value of l.
Simple Challenge (Problem 1)



e=3, |m1|=|m2|=70bit, |m3|=60bit,
|C|=271bit, Spk=496bit.
Public Key: (a1, a2, a3)
a1=4216248180031011146690575580257341486535115078654
976400520752,
a2=208869165457570245222440738684785581895155696351
766440092890,
a3=4951760157160646877071445121,

Ciphertext:
C=2705115812533065994890435027746622671903663976554
366975771320953354957495525975980,


Density: D=1.18,
Rate: R=0.738.
Simple Challenge (Problem 2)



e=3, |m1|=|m2|=100bit, |m3|=80bit,
|C|=381bit, Spk=706bit.
Public Key: (a1, a2, a3)
a1=471205082208439935513040081015231844787050112863
0600393697566890496050275349179498455,
a2=2392605233304211196064298393364530250559239840634
533709773526463062616120178985993857,
a3=5575186299632655790214576212283927176936387,

Ciphertext:
C=3476253086803090347007542623850376181488350960561
6029296551038135974256115018668613634653566048268
30330760227687509,


Density: D=1.15,
Rate: R=0.735.
～
KM(3)-PKC
In KM(3)-PKC, the system parameter
takes on the special value of e=2.
～
 The difference of KM(3)-PKC from the
KM(3)-PKC is as follows:

The d, inverse element of e, does not exist;
 It is required that γ be a prime number;
 It is required that m3 be an (l-1)bit integer;

Encryption

Letting the messages, m1 and m2 be k-bit
positive integers and m3 be an (l-1)-bit positive
integer.
～
 In KM(3)-PKC, m3 must be converted into l-bit
positive integer ～
m3, in one of the following
manner:
(A) ～
m3 = m3,
(B) ～
m3 = 2m3 + 1.

The ciphertext, C∈Z is obtained as follows:
C = a1 m1 + a2 m2 + a3 ～
m 32
Decryption
Algorithm III
Let the intermediate message M be
M = βγm1 + αγm2 + σ m32. ～
Step 1: The intermediate message M is obtained as follows:
M = u-1 C (mod N).
Step 2: The message m3 can be obtained as follows:
(A) ～
m3 = √σ-1 M (mod γ), where m3～
< γ／2.
(B) ～
m3 = √σ-1 M (mod γ), where m3～
is odd.
Step 3: The messages m1 and m2 can be decoded as follows:
～2)／γ,
M’ = (M-σm
3
m1 = β-1 M’ (mod α),
m2 = α-1 M’ (mod β).
Small Example

～
γ= 67, m3(5bit) ⇒ m3(6bit)
～ = 25
(A) m3 = 25
⇒m
3
～
m3 = 11001(2) ⇒ m3 = 011001(2)
～ 2 = 252 = 22 (mod 67)
m
3
√22 = 25, 42
From 25 < 32, ⇒ m3 = 25
～ = 2×25+1 = 51
(B) m3 = 25
⇒m
3
～
m3 = 11001(2) ⇒ m3 = 110011(2)
～
m32 = 512 = 55 (mod 67)
√55 = 16, 51
～ =51 ⇒ m =(51-1)/2 =25
From 51 is odd, ⇒ m
3
3
Very Simple Challenge (Problem 3)



e=2, |m1|=|m2|=40bit, |m3|=60bit,
|C|=183bit, Spk=347bit.
Public Key: (a1, a2, a3)
a1=6543367536282185388250417633736870201483064,
a2=2783954299710691305821534577358205710303709,
a3=2305843051400315201,

Ciphertext:
C=8879117557211732475632383408224638143725814677467
344967,


Density: D=1.10,
Rate: R=0.765.
Simple Challenge (Problem 4)



e=2, |m1|=|m2|=60bit, |m3|=90bit,
|C|=273bit, Spk=517bit.
Public Key: (a1, a2, a3)
a1=114341254641525981448924579807919605890947340267
29571667432317794,
a2=7461681489880664813018893960308318511511063634976
867115019150633,
a3=2475880078581799978444855949,

Ciphertext:
C=1227474490885840279100068964448673718831230559399
0493582056355616755673365289877034,


Density: D=1.11,
Rate: R=0.769.
Security
(1) against LDA
Letting (m1, m2, m3e) be (x1, x2, x3),
we see that the deciphering KM(3)-PKC is
equivalent to the solving of the following
linear Diophantine equation:
C = a1 x1 + a2 x2 + a3 x3.
Security
(2) against Exhaustive Search
In KM(3)-PKC, the ciphertext C is given by
C = a1 m1 + a2 m2 + a3 m3e.
^ 3.
Let the estimated value of m3 be denoted by m
^ =m holds, we obtain the following ciphertext C
When m
3
3
which is equivalent to two terms public key
cryptosystem:
C = a1 m1 + a2 m2
It is easy to see that the ciphertext C can be easily
deciphered.
Thus, in order to make the proposed scheme
invulnerable to the exhaustive search on m3, it is
recommended that m3 satisfy the following:
| m3 | ≧ 60 (in bits).
Challenge (Problem 5)



e=3, |m1|=|m2|=145bit, |m3|=108bit,
|C|=544bit, Spk=1021bit.
Public Key: (a1, a2, a3)
a1=183780376645109679065040324641004896652000191567018194
5732593044189042533219306827122369110561745698647344768
138499333132,
a2=164180314810966321779961694577834938261874000997589532
3655024165395685302638728905242673707686094190861074314
211467612458,
a3=336999333339382997433337688652922450793626119831298813
4821046452501,

Ciphertext:
C=290472351498959655725161617766771997538617375795917060
5096880389428611660258368759429530969625630540447576211
3188527058446634331524729676753767760446069838803208337
Challenge (Problem 6)



e=2, |m1|=|m2|=118bit, |m3|=176bit,
|C|=533bit, Spk=1011bit.
Public Key: (a1, a2, a3)
a1=8260565380024434152622651732509143416287882296136141964
5470365947594165743936450342502652888378093446883047471
041947017303219,
a2=1979356524059643157371699507290007929896105806873908961
5021837665711402995805209520410079245556596544010565108
767377976865302,
a3=3064991081731777716716830940439406147138775777549308003,

Ciphertext:
C=19192110111388738363394577407898165560182991562517650065
1997080874102704794722185274189703097964080199756056231
15869743172503119529435179359158544847722430740294.
むすび





積和型暗号について，より安全性の高い構成法と
して三項暗号を提案した．
公開鍵サイズが 347 ビット，暗号文サイズ183
ビットの挑戦問題を “Very Simple Challenge” と
して提出した．
“Simple Challenges” として公開鍵サイズ 500,
700 ビット程度の挑戦問題を提出した．
“Challenges” として公開鍵サイズ 1000 ビット程
度の問題を提出した．
これらの問題に対して，エレガントな解読を求む．

Download Report