(12) United States Patent
`Miyaji
`
`US006697946B1
`(io) Patent No.: US 6,697,946 Bl
`(45) Date of Patent:
`Feb. 24,2004
`
`(54) MESSAGE RECOVERY SIGNATURE
`APPARATUS
`
`(75) Inventor: Atsuko Miyaji, Noumi-gun (JP)
`
`(73) Assignee: Matsushita Electric Industrial Co.,
`Ltd., Osaka-fu (JP)
`
`( * ) Notice: Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`09/341,658
`Jan. 28, 1997
`PCT/JP97/00181
`
`(21) Appl. No.:
`(22) PCT Filed:
`(86) PCT No.:
`§ 371 (c)(1),
`(2), (4) Date: Jul. 15, 1999
`(87) PCT Pub. No.: WO98/33159
`PCT Pub. Date: Jul. 30, 1998
`Int. Cl.7.................................................... H04L 9/00
`(51)
`(52) U.S. Cl............................... 713/180; 380/28; 380/30;
`380/44; 380/46
`(58) Field of Search ............................... 380/28, 29, 30,
`380/255, 259, 44, 286; 713/176, 180
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`5,136,642 A * 8/1992 Kawamura et al............. 380/282
`5,600,725 A * 2/1997 Rueppel et al.................... 380/30
`
`6,141,420 A * 10/2000 Vanstone et al................... 380/30
`OTHER PUBLICATIONS
`Paar,Fleischmann,Rodriguez, Fast Arithmetic for Public
`Key Algorithm in Galois Fields with Composite Exponents,
`IEEE Transaction on Computers, Oct. 1999, vol. 48,pp.
`1-26.*
`Menezes, Dorschot, Vanstone (Handbook of Applied Cryp­
`tography) CRC Press 1996 pp. 80-81.*
`“Cryptography, Zero-Knowledge Proof, and Number
`Theory,” T. Okamoto & K. Ohta eds., Kyoritysu 1995.
`Cryptography: Theory and Practice, by D. R. Stinson,
`Kyoritsu 1996.
`* cited by examiner
`Primary Examiner—Ayaz Sheikh
`Assistant Examiner—Hosuk Song
`ABSTRACT
`(57)
`A management center 520 determines a public key y4 of a
`user A 510 using the user A’s secret key xA and announces
`the public key y.A to a user B 530. The user A 510 repeats
`generation of a random number k and calculation of r1=gZ:
`(mod p) and r2=f(r1,m)=r1+m(mod p) until r2 and q meet a
`condition r2<q. If the condition is met, the user A 510 finds
`s by calculating sk=(r2+S+1 )+r2xA(mod q) and sends a
`ciphertext (r2,s) to the user B 530. The user B 530 rejects the
`ciphertext if q=r2. If r2<q, the user B 530 recovers a
`message m by calculating ri=g*=g(r2+i+1)/iyA^(mod p) and
`f-1(r1,r2)=m(mod p). With this procedure, a highly secure
`message recovery signature apparatus is realized.
`
`28 Claims, 11 Drawing Sheets
`
`_____________________^520
`
`MANAGEMENT CENTER
`(p, q, g, f, ha, hb, he)
`
`USERA
`(SIGNATURE
`APPARATUS)
`
`USERB
`(RECOVERY
`APPARATUS)
`
`MOBILEIRON, INC. - EXHIBIT 1005
`Page 001
`
`

`

`U.S. Patent
`
`Feb.24, 2004
`
`Sheet 1 of 11
`
`US 6,697,946 Bl
`
`FIG. 1
`
`520
`
`MANAGEMENT CENTER
`(p, q, g, f, ha, hb, he)
`
`USERA
`(SIGNATURE
`APPARATUS)
`
`USERB
`(RECOVERY
`APPARATUS)
`
`MOBILEIRON, INC. - EXHIBIT 1005
`Page 002
`
`

`

`U.S. Patent
`
`Feb.24, 2004
`
`Sheet 2 of 11
`
`US 6,697,946 Bl
`
`FIG. 2
`
`PUBLIC NETWORK 540
`
`MESSAGE m
`
`MOBILEIRON, INC. - EXHIBIT 1005
`Page 003
`
`

`

`U.S. Patent
`
`Feb.24, 2004
`
`Sheet 3 of 11
`
`US 6,697,946 Bl
`
`FIG. 3
`
`PUBLIC NETWORK 540
`
`MOBILEIRON, INC. - EXHIBIT 1005
`Page 004
`
`

`

`U.S. Patent Feb. 24,2004 Sheet 4 of 11
`
`US 6,697,946 Bl
`
`FIG. 4
`
`PUBLIC NETWORK 540
`
`MOBILEIRON, INC. - EXHIBIT 1005
`Page 005
`
`

`

`U.S. Patent
`
`Feb.24, 2004
`
`Sheet 5 of 11
`
`US 6,697,946 Bl
`
`MOBILEIRON, INC. - EXHIBIT 1005
`Page 006
`
`

`

`U.S. Patent
`
`Feb.24,2004
`
`Sheet 6 of 11
`
`US 6,697,946 Bl
`
`FIG. 6
`
`MOBILEIRON, INC. - EXHIBIT 1005
`Page 007
`
`

`

`U.S. Patent
`
`Feb.24, 2004
`
`Sheet 7 of 11
`
`USERA J*
`REQUEST FOR
`NOTIFICATION
`GENERATING
`OF SECRET KEY
`SECRET KEY .
`SECRET KEY
`GENERATION
`SECRET KEY
`REQUEST
`NOTIFYING UNIT
`ACCEPTING UNIT
`v16 A ^15
`5, ^12
`SECRET KEY
`SECRET KEY
`NOTIFICATION
`GENERATING
`PATTERN
`UNIT
`GENERATING UNIT
`, ^13
`GENERATING UNIT —>PUBLIC KEY
`PUBLIC KEY
`ANNOUNCING UNIT
`
`FIG. 7
`
`—>
`
`US 6,697,946 Bl
`
`14
`
`TO ALL
`USERS
`
`MOBILEIRON, INC. - EXHIBIT 1005
`Page 008
`
`

`

`U.S. Patent
`
`US 6,697,946 Bl
`
`Feb.24, 2004
`Sheet 8 of 11
`FIG. 8
`
`31
`
`12 CONTROLLING
`UNIT
`MESSAGE INPUTTING UNIT
`BINARY RANDOM NUMBER
`(CONVERT MESSAGE INTO
`GENERATING UNIT
`NUMBER AND STORE
`(GENERATE k)
`CONVERTEDMESSAGE m)
`
`TO 12 CONTROLLING q-r2-°
`UNIT 31
`
`q-12>0
`
`MOBILEIRON, INC. - EXHIBIT 1005
`Page 009
`
`

`

`U.S. Patent
`
`Feb.24, 2004
`
`Sheet 9 of 11
`
`US 6,697,946 Bl
`
`FIG. 9
`
`FROM BINARY RANDOM FROM ELIMINATING
`NUMBER GENERATING UNIT 37
`
`MOBILEIRON, INC. - EXHIBIT 1005
`Page 010
`
`

`

`US 6,697,946 Bl
`
`U.S. Patent Feb. 24,2004 Sheet 10 of 11
`FIG. 10
`
`RECEIVING UNIT p 41
`12 AND s ,42
`^43
`REJECTING UNIT
`q STORING
`(COMPUTE 12-q. IF COMPUTATION DOES NOT
`UNIT
`YIELDPOSmVENUMBER, REJECTMESSAGE)
`44 REFERENCE
`47\
`46
`45| Is STORING
`yA STORING
`g STORING
`12 STORING
`I UNIT
`UNIT
`UNIT
`UNIT
`48
`CALCULATING UNIT
`49
`
`m
`
`MOBILEIRON, INC. - EXHIBIT 1005
`Page 011
`
`

`

`U.S. Patent
`
`Feb.24, 2004
`
`Sheet 11 of 11
`
`US 6,697,946 Bl
`
`FIG. 11
`
`MOBILEIRON, INC. - EXHIBIT 1005
`Page 012
`
`

`

`US 6,697,946 Bl
`
`1
`MESSAGE RECOVERY SIGNATURE
`APPARATUS
`
`2
`<Signature and Transmission>
`The user A 610 generates a random number k (S644),
`calculates
`
`(Equation 1.1)
`
`FIELD OF THE INVENTION
`The present invention relates to an apparatus for perform­
`ing secret communications and digital signatures by a public
`key cryptosystem, and especially relates to a message recov­
`ery signature apparatus whose security is based on the
`discrete logarithm problem.
`DESCRIPTION OF THE PRIOR ART
`Nyberg-Rueppel proposes a message recovery signature
`scheme which is carried out by a public key cryptosystem
`using the discrete logarithm problem as a basis for security
`(see Nyberg & Rueppel “A New Signature Scheme Based on
`the DS A Giving Message Recovery” 1st ACM Conference
`on Computer and Communications Security (1993)).
`“Discrete logarithm” is a logarithm over a finite field.
`“Discrete logarithm problem” is as follows. Let p be a
`prime number or a prime number raised to a given power, g
`be a primitive root of a finite field GF(p), and y, p, and g be
`any elements of GF(p) aside from zero. The problem is to
`find an integer x that satisfies
`y=gx
`where 0 = x=p-l.
`“Using the discrete logarithm problem as a basis for
`security” is due to the following reason. Though the expo­
`nential calculation is easy, the above logarithmic calculation
`is extremely difficult for a large finite field GF(p), such as
`GF(2127) Such a logarithmic calculation corresponds to the
`calculation of the inverse of a one-way function and thus
`assists in the security of encryption.
`“Public key cryptosystem” is a cryptosystem that uses
`different keys for encryption and decryption, with the
`decryption key being kept secret and the encryption key
`being made public. Public key encryption provides a con­
`venient method for managing the separate encryption keys
`of many users, and so has become a fundamental technique
`for performing communications with a large number of
`users.
`“Message recovery signature” is a signature for certifying
`the validity of the signer, with the message being embedded
`within the signature. With this technique, the message and
`the signature do not have to be sent separately, so that the
`traffic for transmission can be reduced.
`FIG. 11 is a sequential view showing the processing of the
`above conventional signature scheme.
`Auser A 610, a management center 620, and a user B 630
`are connected with each other via a network. Here, the user
`A 610 signs a message m and sends it to the user B 630 under
`management of the management center 620.
`<Public Key Generation>
`A prime number is set as p, an element of GF(p) is set as
`g, and the order of g is set as q as the system conditions.
`Which is to say, q is the smallest integer that satisfies
`(Equation 1.2)
`^=l(mod p)
`First, the management center 620 generates a public key
`y.A for the user A 610 using the user A’s secret key xA which
`has been informed beforehand, according to
`(Equation 1.3)
`yA=g^
`(S640~S641).The management center 620 then reveals
`the system parameters p, q, and g together with the public
`key y.A of the user A 610 to the user B 630 (S643)
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`ri=gA(m°d p)
`
`r2=w/ri(mod p)
`
`r2'=r2(mod 0)
`
`5=^-r2'xx(mod q)
`
`(Equation 1.4)
`
`(Equation 1.5)
`
`(Equation 1.6)
`
`(Equation 1.7)
`
`in sequence (S645-S648), and sends s and r2 to the user B
`630 as a ciphertext (r2,s) (S649).
`Here, r, is referred to as a commitment, Equation 1.5 as
`a message-mask equation, and Equation 1.7 as a signature
`equation. Equation 1.7 leads to the following six types of
`
`ak=b+cxA(m.od q)
`
`(Equation 1.8)
`
`where (a,b,c) is a permutation of (l,r2',s), that is,
`a=l, b=r2', c=s
`a=l, b=s, c=r2'
`a=r2', b=l, c=s
`a=r2', b=s, c=l
`a=s, b=r2', c=l
`a=s, b=l, c=r2'
`Note that (mod p) and (mod q) denote operations modulo
`p and q, respectively.
`<Message Recovery>
`The user B 630 receives the ciphertext (r2,s) and recovers
`the message m by computing
`
`yyg r2=m(mod p)
`
`(Equation 1.9)
`
`with the revealed public key y.A and system parameters p, q,
`g, a, b, and c (S650). Equation 1.9 is derived from
`
`(Equation 1.10)
`
`m = riri
`= A2
`_ s+r2' xA
`- g r2
`= gstAAr2'r2
`= gsyt'r2
`
`Thus, the above conventional scheme is a breakthrough in
`the sense that message recovery signatures by a public key
`cryptosystem based on the discrete logarithm problem are
`made possible for the first time.
`Nevertheless, this conventional scheme is vulnerable to
`four types of attack given below.
`(Signature-equation Attack)
`The signature-equation attack is as follows.
`If a forger acquires the message m and its signature (r2,s),
`the forger can forge a new message mg7 (d is any element
`of GF(p)), sign the message mg7, and send it to the user B.
`Which is to say, the forger sends a ciphertext (r2,s+d) to
`the user B. The user B then calculates
`
`g^y'f'ri =g‘yr^r1gd
`= mgd
`
`(Equationl.il)
`
`If the recovered message mg7 is intelligible, the user B
`will think that the message is from the user A. Hence the
`
`MOBILEIRON, INC. - EXHIBIT 1005
`Page 013
`
`

`

`US 6,697,946 Bl
`
`3
`forger can successfully sign the new message mgrf without
`knowledge of the secret key x.v
`(Homomorphism Attack)
`The homomorphism attack is as follows.
`If a forger chooses a message mm, has the user A sign the
`message mm, and acquires the signature, the forger can
`impersonate the user A and sign a desired message mmg'/.
`This attack is possible for the same reason as the
`signature-equation attack. The difference with the signature­
`equation attack is that the forger can sign the desired
`message mmg‘i.
`(Redundancy Attack)
`The redundancy attack is as follows.
`If a forger acquires the message m and its signature (r2,s),
`the forger can sign a new message mm that satisfies
`
`5
`
`10
`
`15
`
`rr2=r2'+nq(ytr^)
`
`mm=rr2x(m/r2)
`
`(Equation 1.12)
`
`(Equation 1.13)
`
`Which is to say, the forger sends a ciphertext (rr2,s) to the
`user B. Then the user B computes
`
`20
`
`gsy"2'rr2 = gsy'f'rr2
`= (m/r2)rr2
`= mm
`
`(Equation 1.14)
`
`If the recovered message mm is intelligible, the user A
`will think that the message is from the user A.
`This attack is based on redundancy between r2' used in
`Equation 1.7 and r2 calculated in Equation 1.6.
`(Recovery-equation Attack)
`The recovery-equation attack is as follows.
`Without performing communications beforehand, a forger
`can sign a message My.,' (e is an element of GF(p)) using
`any new M (M is an element of GF(p)).
`Specifically, the forger determines rr2 and ss that satisfy
`
`rr2=Myugv (where u and v are elements of GF(jj)) (Equation 1.15)
`
`25
`
`30
`
`35
`
`4
`Advances in Cryptology-Proceedings of Eurocrypt ’94, Lec­
`ture Notes in Computer Science, vol.950 (1995) Springer­
`Verlag, pp.182-193.
`Thus, the conventional message recovery signature
`scheme is weak against the four attacks that can forge
`signatures of messages which satisfy certain conditions.
`
`DISCLOSURE OF THE INVENTION
`In view of the stated problems of the conventional sig­
`nature scheme, the present invention aims to provide a
`message recovery signature apparatus that is secure against
`the above four attacks.
`The above object can be fulfilled by a message recovery
`signature apparatus for signing a message m with a secret
`key x_, using a discrete logarithm problem as a basis for
`security, based on operations performed on a finite field
`GF(p) where p is a prime number and g is an element whose
`order is q, the message recovery signature apparatus includ­
`ing: a random number generating unit for generating a
`random number k; a commitment generating unit for gen­
`erating a commitment r, from the random number k accord­
`ing to a function I , ,(k)=gz; a message masking unit for
`generating a masked message r2 from the commitment r,
`and the message m according to a function f^r^m) that
`maps GF(p)xGF(p) into the finite field GF(p); and a signa­
`ture generating unit for generating a signature s from the
`masked message r2 and the secret key x_, according to a
`function fl3(r2,x.A) the message recovery signature apparatus
`being characterized in that the function f12(r1,m) has a
`property that when gJ/1 denotes a public key y_, and t, j, and
`e denote elements of a finite ring Zq={0, 1, . . . , q-1}, the
`three variables t, j, and e are unable to be replaced with two
`algebraic relations in l'l2(g'y.,',my.,') and l'l2(g'y.,',mg').
`With this construction, substituting Mge or My.,' for the
`message m cannot determine the three variables t, j, and e
`that satisfy r2=f12( ). Also, the inverse f-1 of the map f is
`
`55=- v
`
`e=rr2+u
`
`40
`
`and
`
`(Equation 1.16)
`
`(Equation 1.17)
`
`^(rjg.r^im.g-)
`
`T1(ri/y2iZ2)*(|>(m,^)
`
`and sends a ciphertext (rr2,ss) to the user B. The user B then
`calculates
`
`gssy"2' rr2 = yeA My
`
`(Equation 1.18)
`
`If the recovered message My.,' makes sense, the user B
`will think that the message is from the user A.
`This attack is based on that, for the elements u and v of
`GF(p), there are solutions that satisfy
`
`rr2=MyA“gv
`
`(Equation 1.19)
`
`v=-b!a (where a and b are elements of {1.s j ) (Equation 1.20)
`
`The above four attacks are detailed in Atsuko Miyaji
`Weakness in Message Recovery Signature Schemes 1 Insti­
`tute of Electronics, Information, and Communication
`Engineers, Information Security Workshop (July 1995),
`Nyberg & Rueppel “A New Signature Scheme Based on the
`DS A Giving Message Recovery” 1st ACM Conference on
`Computer and Communications Security (1993), and
`Nyberg & Rueppel “Message Recovery for Signature
`Schemes Based on the Discrete Logarithm Problem”
`
`45
`
`50
`
`55
`
`60
`
`65
`
`respectively for arbitrary functions <|) and <|) of two variables.
`Accordingly, the recovery-equation attack and the homo­
`morphism attack can be avoided.
`Here, the signature generating unit may calculate, when
`Zq={0, 1, . . . , q-1} is a finite ring and ha, hb, and he are
`functions that map ZqxZqxZq into Zq, a signature s which
`satisfies
`
`Aa(r2',5;l)A:=A£’(r2'A5;l)+Ac(r2',5;l)xy4(mod <?)
`
`where the functions ha, hb, and he satisfy conditions (1) and
`(2):
`
`(1) if ha(r2’,s,l)=ha(rr2’,ss,l) and hc(r2’,ss,l)=hc(rr2’,ss,
`1), then hb(r2,,s,l)-ha(r2,,s,l)^hb(rr2,,ss,l)
`(2) if ha(r2’,s,l)=ha(rr2’,ss,l) and hb(r2’,s,l)=hb(rr2’,ss,
`1), then hc(r2’,s,l)-ha(r2’,s,l)?shc(rr2,ss,l)
`for any elements rr2’ and ss of the finite ring Zq aside from
`a few prefixed values.
`With this construction, a forger who tries to sign a
`message mg^ cannot find rr2f and ss which satisfy the
`signature equation (that is, rr2’=ss=0). Accordingly, the
`signature-equation attack can be avoided.
`Here, the message recovery signature apparatus may
`further include: a judging unit for judging whether the
`masked message r2 generated by the message masking unit
`
`MOBILEIRON, INC. - EXHIBIT 1005
`Page 014
`
`

`

`5
`meets a condition 0<r2<q; and a repeating unit for having,
`when the judging unit judges that the condition is unmet, the
`random number generating unit, the commitment generating
`unit, and the message masking unit respectively generate a
`new random number k, a commitment r1; and a masked
`message r2.
`With this construction, the redundancy between r2 and r2'
`is eliminated. Accordingly, the redundancy attack can be
`avoided.
`Here, the operations may be performed on a finite field
`Gl(p') instead of a finite field GF(p).
`Here, the operations may be performed on an elliptic
`curve E(GF(p)) or E(GF(pr)) instead of a finite field GF(p).
`With this construction, faster message recovery signature
`processing and recovery processing, strengthened security,
`and compact circuitry and software implementations can be
`achieved.
`BRIEF DESCRIPTION OF THE DRAWINGS
`FIG. 1 shows the configuration of the first embodiment of
`a products trading system that uses a message recovery
`signature apparatus of the present invention.
`FIG. 2 shows the detailed hardware construction of the
`message recovery signature apparatus (user A) 510 of the
`present invention.
`FIG. 3 shows the detailed hardware construction of a
`management center 520.
`FIG. 4 shows the detailed hardware construction of a
`recovery apparatus (user B) 530.
`FIG. 5 is a sequential view showing the message recovery
`signature algorithm and data exchange in the first embodi­
`ment.
`FIG. 6 is a sequential view showing the message recovery
`signature algorithm and data exchange in the second
`embodiment.
`FIG. 7 is a block diagram showing the construction of a
`management center 1 of the third embodiment.
`FIG. 8 is a block diagram showing the construction of a
`message recovery signature apparatus (user A) of the third
`embodiment.
`FIG. 9 is a block diagram showing the detailed construc­
`tion of a SK unit 38 shown in FIG. 8.
`FIG. 10 is a block diagram showing the construction of a
`recovery apparatus (user B) of the third embodiment.
`FIG. 11 is a sequential view showing the procedure of the
`conventional message recovery signature scheme.
`DESCRIPTION OF THE PREFERRED
`EMBODIMENTS
`The following is a detailed description of a message
`recovery signature apparatus of the present invention with
`reference to the figures.
`First Embodiment
`FIG. 1 shows the configuration of the first embodiment of
`a products trading system that uses a message recovery
`signature apparatus of the present invention.
`This system includes a management center 520 which
`manages communications for products trading, a user A 510
`as an orderer of products, a user B 530 as a seller of the
`products, and a public network 540 which connects the
`management center 520 and the users in the system. In this
`system, message recovery signatures by encryption are used
`to place orders for products in order to ensure safe products
`trading.
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 6,697,946 Bl
`
`6
`The user A 510 is a message recovery signature apparatus
`of the present invention and is roughly made up of a
`transmitting/receiving unit 511 connected to an internal bus
`516, a processor 512, an inputting unit 513, a system
`parameter storing unit 514, and a random number generating
`unit 515, as shown in FIG. 2.
`The transmitting/receiving unit 511 is a communication
`interface, such as a modem, which connects the public
`network 540 with the internal bus 516.
`The processor 512 is a CPU or the like equipped with a
`calculating unit 512a and a controlling ROM 512b storing a
`control program unique to the signature apparatus 510, and
`performs calculations and transmission control for signa­
`tures according to a certain procedure (described later), as
`well as controlling each component of the signature appa­
`ratus 510.
`The inputting unit 513 is a keyboard or an I/O (input­
`output) port that receives a secret key xA and a message m.
`The system parameter storing unit 514 is a RAM or the
`like that temporarily stores system parameters downloaded
`from the management center 520. System parameters
`referred to here are parameters necessary for the message
`recovery signature scheme used in the present system and
`have been made public.
`The random number generating unit 515 generates a
`random number which is a positive integer within a range
`designated by the processor 512.
`The management center 520 is an apparatus for managing
`the system parameters and is equipped with a transmitting/
`receiving unit 521 connected to an internal bus 524, a
`processor 522, and a system parameter storing unit 523, as
`shown in FIG. 3.
`The transmitting/receiving unit 521 is a communication
`interface, such as a modem, that connects the public network
`540 with the internal bus 524.
`The processor 522 is a CPU or the like equipped with a
`calculating unit 522a and a controlling ROM 522b storing a
`control program unique to the management center 520, and
`performs public key generation and system parameter trans­
`mission for each user according to a certain procedure
`(described later), as well as controlling each component of
`the management center 520.
`The system parameter storing unit 523 is a ROM or the
`like that prestores the system parameters necessary for the
`message recovery signature scheme of the present system.
`The user B 530 is a recovery apparatus for recovering a
`message sent from the user A 510 and is roughly made up of
`a transmitting/receiving unit 531 connected to an internal
`bus 535, a processor 532, a system parameter storing unit
`533, and a displaying unit 534, as shown in FIG. 4.
`The transmitting/receiving unit 531 is a communication
`interface, such as a modem, that connects the public network
`540 with the internal bus 535.
`The processor 532 is a CPU or the like equipped with a
`calculating unit 532a and a controlling ROM 532b storing a
`control program unique to the recovery apparatus 530, and
`performs message recovery according to a certain procedure
`(described later), as well as controlling each component of
`the recovery apparatus 530.
`The system parameter storing unit 533 is a RAM or the
`like that temporarily stores the system parameters down­
`loaded from the management center 520.
`The displaying unit 534 is a CRT (Cathode-Ray Tube) or
`the like that displays a recovered message. If the message
`displayed on the displaying unit 534 makes sense, the user
`B 530 verifies that the message (order) is from the user A
`510.
`
`MOBILEIRON, INC. - EXHIBIT 1005
`Page 015
`
`

`

`7
`The public network 540 is a public telephone network or
`ISDN (Integrated Services Digital Network). Communica­
`tions in the present system are performed by the Internet
`with the public network 540 as a physical layer and TCP/IP
`(Transmission Control Protocol/Internet Protocol) as an
`intermediate layer.
`The operation of the present system with the above
`configuration will be explained below.
`FIG. 5 shows the message recovery signature algorithm
`and data exchange between the three parties (user A 510,
`management center 520, and user B 530) in the present
`system and corresponds to FIG. 11 of the conventional
`scheme.
`<System Conditions>
`The system conditions of the message recovery signature
`scheme in the present system are as follows.
`The message recovery signature scheme used in this
`system is a public key cryptosystem that uses the discrete
`logarithm problem as the founding principle for the security,
`and is based on operations over a finite field GF(p) where p
`(512 bits long) is a prime number, g is an element, and q (256
`bits long) is the order of g. Here, the prime number p and the
`order q are set to be equivalent, that is, p~q.
`A map f( ) from GF(p)xGF(p) to GF(p) is defined as
`
`5
`
`10
`
`15
`
`20
`
`25
`
`/(r1,m)=r1+m(mod p)
`
`(Equation 2.1)
`
`and the inverse f-1 of f is defined as
`
`P1 (rl, f (n, m)) = f (n, m) - n
`= m
`
`(Equation 2.2)
`
`30
`
`Here, the message m is a value representing a combina­
`tion of binary numbers obtained when, for example, “I
`would like to order a product ABC. My identification code
`is 1234.” is expressed in a character code such as the shifted
`JIS code.
`Meanwhile, a signature equation used by the orderer of
`the product is defined as
`
`35
`
`40
`
`ha(r2,s,l)k=hb(r2,s,l)+hc(r2,s,l)xA(mo(l q)
`
`(Equation 2.3)
`
`where ha, hb, and he are maps from ZqxZqxZq to Zq (where
`Zq={0, 1, . . . , q-1} and are set in the present embodiment
`respectively as follows:
`
`45
`
`ha(r2',s,l)=s
`
`hb(r2,s,l)=r2+s+l(moii q)
`
`Ac(r2,,-S',l)=r2l
`
`(Equation 2.4)
`
`(Equation 2.5)
`
`(Equation 2.6)
`
`The system parameters (p, q, g, f, ha, hb, he) that define
`the above system conditions have been stored in the system
`parameter storing unit 523 in the management center 520 in
`advance.
`<Public Key Generation>
`The management center 520 generates a public key y.A of
`the user A 510 using the element g of GF(p) and the user A’s
`secret key xA which has been informed by the user A 510 by
`communication or a confidential letter (S550), according to
`the following equation
`
`v.^y’1
`
`(Equation 2.7)
`
`(S551). More specifically, the processor 522 has the
`calculating unit 522a perform the above exponentiation
`according to the program stored in the controlling-ROM
`
`50
`
`55
`
`60
`
`65
`
`US 6,697,946 Bl
`
`8
`522b, using the user A’s secret key xA received via the
`transmitting/receiving unit 521 and the system parameter g
`read from the system parameter storing unit 523.
`The management center 520 then announces the system
`parameters (p, q, g, f, ha, hb, he) to the user A 510 and the
`user B 530, and informs the user B 530 of the user A’s public
`key y.A (S552 and S553).
`<Signature and Transmission>
`The user A 510 signs and transmits the message m
`according to the following procedure (S554-S559).
`(Step S554)
`To place an order with the user B 530 for the product, the
`user A 510 first stores the received system parameters in the
`system parameter storing unit 514 and generates a random
`number k (512 bits long).
`Specifically, in accordance with the program in the con­
`trolling ROM 512b, the processor 512 stores the system
`parameters received via the transmitting/receiving unit 511
`in the system parameter storing unit 514, has the random
`number generating unit 515 generate the random number k
`on GF(p), and acquires the random number k.
`(Step S555)
`The user A 510 then finds a commitment r, by computing
`
`(Equation 2.8)
`/■|=A'm°cl P)
`More specifically, in accordance with the program in the
`controlling ROM 512b, the processor 512 reads g from the
`system parameter storing unit 514 and has the calculating
`unit 512a perform the above exponentiation modulo p
`through use of g and the random number k.
`(Step S556)
`The user A 510 further finds r2 as follows:
`
`r2=fltri,m)
`= n + m (mod p)
`
`(Equation 2.9)
`
`Specifically, the processor 512 receives the message m
`from the inputting unit 513 and has the calculating unit 512a
`perform the above addition modulo p for m and r, obtained
`in step S555.
`(Step S557)
`The processor 512 then compares r2 and q according to
`the program in the controlling ROM 512b. If q=r2, steps
`S554-S556 are repeated.
`(Step S558)
`If, on the other hand, r2<q, the user A 510 solves s from
`the signature equation
`
`ha(r2\s,l)k=hb(r2,s,l)+hc(r2,s,l)xA(moii q)
`
`(Equation 2.10)
`
`that is
`
`5£=(r2+5+l)+r2xA(m°d q)
`(Equation 2.11)
`More specifically, the processor 512 receives the secret
`key x.A via the inputting unit 513 and has the calculating unit
`512a solve s modulo q.
`(Step S559)
`Lastly, the user A 510 sends a ciphertext (r2,s) to the user
`B 530.
`Specifically, the processor 512 sends the ciphertext (r2,s)
`to the user B 530 via the transmitting/receiving unit 511.
`<Message Recovery>
`(Step S560)
`The user B 530 compares r2 with q on receiving the
`system parameters and the ciphertext (r2’s).
`Specifically, in accordance with the program stored in the
`controlling ROM 532b, the processor 532 temporarily holds
`
`MOBILEIRON, INC. - EXHIBIT 1005
`Page 016
`
`

`

`9
`the ciphertext (r2,s) received via the transmitting/receiving
`unit 531 and has the calculating unit 532a compare r2 with
`q read from the system parameter storing unit 533.
`(Step S561)
`If q = r2, the user B 530 rejects the signature.
`Here, the processor 532 displays on the displaying unit
`534 that message recovery for the ciphertext (r2,s) received
`from the user A 510 ended in failure.
`(Step S562)
`If r2<q, the user B 530 finds r, by computing
`
`5
`
`10
`
`US 6,697,946 Bl
`
`10
`Therefore, the recovery-equation attack and the homo­
`morphism attack can be prevented.
`Concerning the signature equation, in the conventional
`scheme a set of coefficients (a,b,c) is a permutation of
`(r2',s,l) as shown in Equation 1.8, whereas in the present
`embodiment (a,b,c) is defined using the maps ha, hb, and he.
`Assume that r2' and s are elements of Zq, then the maps ha,
`hb, and he satisfy the following two conditions for every rr2,
`and ss aside from a few prefixed values.
`(1) If ha(r2',s,l)=ha(rr2',ss,l) and hc(r2',s,l)=hc(rr2',ss,l),
`then
`
`rl = gk
`= g^^yrp (mod p)
`
`(Equation 2.12)
`
`and recovers the message m according to
`
`/’-1(r1,r2)=m(mod p)
`
`(Equation 2.13)
`
`which can be expanded to
`
`m= f r2)
`= f2 - n
`- ^2 “ g
`= r2-g^^yrp
`
`(Equation 2.14)
`
`More specifically, the processor 532 has the calculating
`unit 532a recover the message m using the system param­
`eters and the user A’s public key y_, revealed by the
`management center 520, and displays the recovered message
`on the displaying unit 534. If the displayed message is an
`intelligible order, the user B 530 authenticates the message
`as being sent from the user A 510.
`With the above message recovery signature scheme of the
`first embodiment, the shortcomings present in the conven­
`tional scheme can be overcome in the following way.
`Concerning the map from p+m to r2, an equation
`
`m = r^ri
`= >-2gsyf
`
`(Equation 2.15)
`
`holds from Equation 1.5 in the conventional scheme.
`Substituting m=Mge (or My.,') and r2=Mg'y.A' (where t, j,
`and e are elements of Zq) yields
`
`(Equation 2.16)
`where the three variables t, j, and e can be replaced with two
`algebraic relations. Hence the map from r, to r2 is a
`homomorphism.
`In the present embodiment, on the other hand, it is clear
`from Equation 2.9 that the map from r, to r2 is not a
`homomorphism, which is to say, three variables t, j, and e
`that are elements of Zq cannot be replaced with two alge­
`braic relations in f(g'yA,myAe) and ^g'yyjmg®). . . .
`(Condition 1).
`In other words, substituting Mge or My.,' for the message
`m cannot determine the three variables t, j, and e that satisfy
`r2=f( ).
`Also, the inverse map f 1 of f defined in Equation 2.2
`establishes the relationship
`
`r1(r1/g,r2)*(|>(m,g)
`
`C1(r1/y/1,r2)*(|>(m,j>/1)
`(Equation 2.17)
`for arbitrary functions <|> and <|> of two variables, respectively.
`
`hb{r2',sX)-ha{r2',sX)^hb{rr2',ssX)
`
`(Equation 2.18)
`
`15
`
`(2) If ha(r2',s,l)=ha(rr2',ss,l) and hb(r2',s,l)=hb(rr2',ss,l),
`then
`
`Ac(r2(s,l)-Aa(r2(s,l)*Ac(rr2',ss,l)
`
`(Equation 2.19)
`
`As is evident from the signature equation (Equations 2.10
`and 2.11) of the present embodiment, a forger who tries to
`sign a message mg'/ cannot find rr2’ and ss which satisfy the
`signature equation (that is, rr2'=ss=0). Hence the signature­
`equation attack can be avoided.
`Further, the signature equation of the present embodiment
`is strong against conventional cryptanalysis that uses pro­
`portional relations, as the equation cannot be decomposed
`into two terms. For details on the cryptanalysis attack using
`proportional relations, see L. Harn & Y. Xu “Design of
`Generalised ElGamal Type Digital Signature Schemes based
`on Discrete Logarithm” Electronics Letters vol. 30 (1994)
`pp.2025-2026.
`Concerning the value of r2, in the conventional scheme
`there is redundancy between r2' in Equation 1.7 and r2 in
`Equation 1.6, whereas in the present embodiment the value
`of r2' is limited to smaller than q.
`Accordingly, rr2 that satisfies Equation 1.12 does not
`exist, so that the redundancy attack is invalid against the
`present signature scheme.
`Therefore, the four attacks which are valid against the
`conventional scheme can be avoided by the message recov­
`ery signature apparatus of the present embodiment.
`While the function f has been set as r,+m in the above
`embodiment, any map that satisfies Condition 1 may instead
`be used, though it is preferable to use a map, such as r ,+m,
`with a small computation amount.
`Also, the maps ha, hb, and he are not limited to those used
`in the above embodiment but any maps that satisfy Equa­
`tions 2.18 and 2.19 can be used, though it is preferable to use
`a map with a small computation amount in order to
`strengthen the security against the conventional cryptanaly­
`sis which uses proportional relations.
`Also, incorporating the maps ha, hb, and he into a
`message recovery signature scheme (e.g. the ElGamal sig­
`nature scheme) different with the above conventional
`scheme can produce the same effect as the above embodi­
`ment.
`The message recovery signature scheme based on opera­
`tions over the finite field GF(p) has been used in the above
`embodiment. However, it is also possible to use a general­
`ized message recovery signature scheme