Step 2: R chooses a random large integer y and sends S Fast GF(p)modular inversion algorithm

Y =gy mod n suitable for VLSl implementation

Step 3: R decrypts X‘ and gets Tao Zhou, Xingjun Wu, Guoqiang Bai and Hongyi Chen
A new, efficient algorithm for modular inversion in Galois field GF@)
and then R computes is presented. Very large scale integration (VLSI) implementation of
the algorithm is described and the high performance and low silicon
k = X? mod n penalty is demonstrated.
Step 4; S computes
k‘ = Y x mod n Introduction: Modular inversion (MI) is a kernel arithmetic operation
necessary for public key cryptosystems [l-31. There are two known
In fact k =g”y = k‘, now S and R share a session key k.
basic classes of algorithms for MI: the repeated exponentiation
Step 5: If S wants to send a message M to R, he will send R both M and
algorithm (REA) and the extended Euclidean algorithm (EEA) [4].
D = H ( k , M) Both involve complex arithmetic operations. The REA, which is
Step 6: R computes derived from the Fermat theorem, is slow, since it involves complex
multiplication and squaring operations. The EEA is simpler but
D’ = H ( k , M) requires division of large operantis, which is time-consuming.
If D =D’, R accepts M otherwise rejects it. In this Letter we introduce a fast algorithm for modular inversion
in prime fields (algorithm MIF’F), which involves only ordinary
Protocol analysis: In this Section, we prove that this scheme is addition/subtraction, and does not need any modular operations or
deniable and secure. multiplication and division by laking the parallelism of hardware
Lemma I : The protocol is deniable. realisation into account. The following is the pseudo-code of algo-
rithm MIPF.
Proof After negotiating a share key with S, R can construct a message
M‘,which is different from M.R can compute
D’ = H ( k , M’) Algorithm MIPF.
(D‘, M’) is indistinguishable from the actual message computed by S, SO Input: p , a prime number and x E (0, p )
R can simulate the authenticated message of S. It follows that the Output: y, satisfying xy = 1 mod p
protocol is deniable.
Step 1; Set u t p ; v t x ; r t 0; s c 1 ; if (x is even), go to Step 3; else,
Lemma 2: The protocol authenticates the source of the message go to Step 4.
Proof If someone proves (D,M) to R, which D = H(k, M), he must be S. Step 2: Set v t -v
Even though an intruder gets all the messages in Step 1 and Step 2, he Step 3: Set v t (v >> I); if (s is positive and even), set s t s >> 1; else,
cannot get the key k. It is as difficult as solving the discrete logarithm if (s is negative and even), set s t ( s > > 1)+p; else, set
problem. s t ( s > > 1)+@>> 1)+ 1; if (v is even), go to Step 3; else, go to
Step 4.
Lemma 3: The protocol resists PIM attack. Step4: S e t u ’ t v ; v t u - v ; u * - u ’ ; y t s .
Step 5: If (u = I), return y ; else, if ( v >o), set r’ t s; s c r - s; r t r’;
Prooj In Step 1, the message is encrypted with K,,. Anyone else
go to Step 3; eke, set r’ c s; s e-s - r; r t r‘; go to Step 2.
cannot get this secret key. An intruder can intercept the message from S
and act as R to negotiate a session key with S. If he wants to complete Note: The ‘ >> 1’ operation in Step 3 means right shifting the binary
the PIM attack, he must act as the sender S to cheat R. He can choose number for one bit with the sign bit extended. The temporary variables,
an integer and get an X,but he cannot construct X‘ without KPN.If he u’ and r’ in Step 4 and Step 5 , which are used to store the last values in
fakes an A”, R cannot get correct X. R and INQ will not get a share the data exchange process, only exist to make the algorithm gramma-
key k. The attack fails. tically correct. They are not needed in the hardware implementation
since the clock-triggered registers can exchange their contents directly.
Conclusion: As the analysis demonstrates, our scheme is a deniable
authentication protocol. It can resist PIM attack. Compared with the
existing scheme, it is much more simple.
Algorithm analysis: The initial values of the variables are: u = p ,
0 IEE 2002 16 October 2001 v =x, r = 0 and s = 1, hence two equations hold:
Electronics Letters Online No: 20020502 xr u modp
D o l : 10.1049/eI:20020502
xs = v modp
Lei Fan, C.X. Xu and J.H. Li (Department of Electronic Engineering,
Shanghai Jiao Tong University, Shanghai 200030, People k Republic It can be seen that (1) and (2) always hold after each iteration of
of China) algorithm MIPF. When the algorithm is finished with u = I , we know
E-mail: leinwpu@163.net xy = 1 modp from (1). The processing speed of algorithm MIPF can be
estimated as follows.
ReferenEes At the end of the ith iteration, u and v are both odd numbers in the
1 DENG, X., LEE, C.H., and ZHU, H.: ‘Deniable authentication protocols’, IEE region (0, p ) , noted as uiand v,, which satisfy the following recursive
Proc., Comput. Digit. Tech., 2001, 148, (2), pp. 101-104 equations:
2 DWORK, c., NAOR, M., and SAHAI, A,:‘Concurrent zero-knowledge’. Proc.
30th ACM STOC’98, Dallas, TX, USA, 1998, pp. 409418
3 AUMANN, Y., and RABIN, M.: ‘Authentication,enhanced security and error
correcting codes’. Crypto’98,
._ Santa Barbara, CA, USA, 1998,
pp. 299-703
4 AUMANN. Y.. and RABIN, M.: ‘Efficient deniable authentication of long where k,,, is a positive integer.
messages’. Int. Conf. on Theoretical Computer Science in honour of It is obvious that at the start of fhe computation v is given the value of
Professor Manuel Blum’s 60th birthday, 1998 (http:i/ x and Step 3 will be repeatedly executed until v = a , which 1s the
www.cs.cityu.edu.hk/dept/video.html) product of the odd factors of x. The original values are then uo = p and
5 DIFFIE, W., and HELLMAN, WE.: ‘New directions in cryptography’, IEEE vo=a. Thus, the sequence for {ut} will be:
Trans. In$ Theory, 1976, 10, (6), pp. 644-654
p - tz
6 SCHNEIER, B : ‘Applied cryptography: protocols, algorithms and source uo = p , u1 = a, u2 = VI = --, . . . , u,+, = u,-I 2kc- u, , . . . , u , = 1
~

code in C’ (John Wiley and Sons Inc., 1996) 2kl

706 ELECTRONICS LETTERS 4th J u l y 2002 Vol. 38 No. 14

It can be deduced from the recursive equation that: 0 IEE 2002 30 January 2002
Electronics Letters Online No: 20020472
Dol: 10.1049/el:20020472
Tao Zhou, Xingjun Wu, Guoqiang Bai and Hongyi Chen (Institute of
The average value ki is 2, since the possibility of ki = t is 2-‘as ki equals Microelectronics, Tsinghua University 100084 Beijing, People ’s
the number of successive zeros in the right-most bits of ui-l - ui. Republic of China)
Therefore ui+l < which means that the length of u is shortened
two bits every two iterations. On average, it will take m iterations for an E-mail: zht@dns.ime,tsinghua,edu.cn
m-bit prime. field GF(p).
References
V U 1 implementation: The arithmetic operations required in algo- 1 DIFFIE,w., and HELLMAN, E.: ‘New directions in cryptography’, IEEE
rithm MIPF include only ordinary addition or subtraction and shifting, Trans. In$ The054 1976, 22, pp. 644-654
therefore implementation has almost no hardware expense. In the 2 RIVEST, R.L., sHAMIR, A , and ADLEMAN, L.: ‘A method for obtaining
digital signatures and public key cryptosystems’, Commun. ACM, 1978,
algorithm’s hardware implementation, one adder will be sufficient for
21, pp. 120-126
all computing processes. The hardware structure is shown in Fig. 1, in 3 MENEZES, A,: ‘Elliptic curve public key cryptosystems’ (Kluwer
which ‘ >> 1’ denotes the hard-wiring right shifting with the left-most Academic Publishers, 1998, 6th ptg.)
sign bit unchanged. 4 MENEZES, A,, VAN OORSCHOT, P.C., and VANSTONE, S.A.: ‘Handbook of
applied cryptology’ (CRC Press, New York, 1997)
stalt , I
clock
~
f ....... 1 J .....________.

40 GHz 7.9 mW low-power frequency

divider IC using self-aligned
selective-epitaxial-growth SiGe HBTs
R. Hayami and K. Washio
A low-power current-mode-logicfrequency divider integrated circuit
(IC) that operated at 40 GHr with a power consumption of 7.9 mW
per master-slave flip-flop was fabricated using 0.2 flm self-aligned
selective-epitaxial-growth SiGe heterojunction bipolar transistors.
This IC also operated at 35 GHz from a supply voltage of -2.2 V.
To the authors’ knowledge this IC consumes the least power of any for
Fig. 1 Architecture for hardware implementation operation in the millimetre-waveband that have appeared to date.

+
The m 1 bit adder is the only computation cost for the case of m bit
Introduction: A high-speed frequency divider is a key circuit for such
applications as multi-gigabit data communications systems and
modulus p . Thus, the implementation of algorithm MIPF has good
microwave/millimetre-wave wide-bandwidth wireless communica-
features in terms of both timing and area, and is faster and less
tions systems. Both low-power consumption and high-speed operation
expensive compared to the other known methods. The complexities
should be achieved to meet the growing demand for these commu-
of the vanous algorithms are compared in Table 1. The modular inverter
based on algorithm MIPF was successfully implemented for 192-bit nication systems. This is because such systems require sophisticated
functions that are only practicable as circuits when large-scale
prime fields in Verilog hardware description language on a Sun work-
integration is applied. SiGe heterojunction bipolar transistors
station platform, synthesised by the Synopsys Design Compiler with
0.6 pm CMOS technology libraries. A realisation of the EEA was also (HBTs) have already demonstrated high-speed performance, with a
cutoff frequency of 120 GHz [l], an emitter coupled logic (ECL) gate
synthesised at the same condition. The synthesis results are compared
in Table 2. It shows that the VLSI implementation of algorithm MIPF is delay of 5.3 ps [2], and divider toggle frequencies of 72 GHz in static
about 3.7 times faster and 30% smaller than that of the EEA. mode and 92 GHz in dynamic mode [3]. An integrated circuit (IC)
chipset for 40 Gbit/s optical-fibre-link systems has also been fabri-
cated and operation up to 50 Gbit/s has been demonstrated [4, 51. The
Table 1: Comparison of complexity of algorithms parasitic elements, i.e. the junction capacitances and series resis-
I I Space complexity
1 Time complexity
(additions) I
tances, are very small in SiGe HBTs with a self-aligned structure [6],
so SiGe HBTs are inherently suitable for low-power operation.
MIPF One adder O(m) Furthermore, the fabrication of an SiGe HBT is almost completely
EEA Three multipliers and four subtractors compatible with the technology used to fabricate CMOS, so the SiGe
0(mZ)
HBT technology is easily extensible to integration with CMOS [7].
REA One multiplier and one subtractor ob3) This is a further big advantage in terms of improving functionality
and reducing the dissipation of power. In this Letter, we describe a
low-power current-mode-logic (CML) frequency divider IC that
Table 2: Comparison of synthesised modular inverters operated at 40 GHz with a power consumption of 7.9mW per
master-slave flip-flop and operated at 35 GHz from a supply voltage
EEA MIPF
of -2.2 v.
Size (equivalent gates) 27869 19571
.
Highest clock freauencv (MHz)~~ I
25 , 40
Cycles for one inversion computation I 1537 I 673 Characteristics of SiGe HBT: The 0.6 pm-wide SiGe-base and
Number of computations per second 1 16 000 I 59 000 Si-cap multilayer of the SiGe HBT was grown by selective epitaxy.
This process was carried out by an ultra-high vacuum/chemical
vapour deposition system. The collector capacitance and base
Conclusion: Algorithm MIPF presented in this Letter is shown to be resistance were effectively reduced by using a poly-Si assisted
better than other known methods and very suitable for hardware self-aligned selective-epitaxial-growth structure [6]. Shallow-trench
implementation. The algorithm’s VLSI implementation was devel- and deep-trench isolation structures were used to reduce the collec-
oped for kemel computing engines in various applications of high- tor and substrate parasitic capacitances. Four-level interconnects
speed public key cryptosystems. were formed by chemical mechanical polishing. Metal-insulator-

ELECTRONICS LETTERS 4th July2002 Vol. 38 No. 14 707