<<

. 5
( 19 .)



>>

worth having.
The more diftku/t
question is how
best to do it.




CRYPTOBvIES SPRING THE TECHNICAL NEWSLETTER OF RSA LABORATORIES
1996 -
Giii
Page 22
Previous Page Home Next Page




HMAC uses the
hash function 1-l
as a black box.
No modifications
to the code for
H are required
to implement
HMAC.




You can™t make
good wine from
bad grapes: if
no strengths are
assumed of the
hash function,
we can™t hope
to justify any
construction
based on if.




S P I? I N G I994 CRYPTOBYIES
THE TECHNICAL NEWSLETTER OF RSA LABORATORIES -
Page 23
Previous Page Home Next Page




A well justified
MAC construction,
in our view is
one under which
the security of
the MAC can be
related as closely
as possible fo
the (assumed)
security
properties of
the underlying
hash function.




CRYPTOBYTES SPRING 1096 - THE TECHNICAL NEWSLETTER OF RSA LABORATORIES
El
Page 24
Previous Page Home Next Page




&rlikckclEhiqr.˜in˜-˜94
BTozkiirgs, lafiarePSXesinChqdzerSzia-czVd.839,
Y. Llssndtd., gairgerwe, EM.
fi I.Llrrgazd.Ads&n˜drci@.eforhssh˜.pd-
vatresin--ckLipto89m,m
bbtes inht&uterSciareVd.435,G. Ezassadd,
srirger-verlag, m9.
w -Irstmti- dTf&nkqy. Eiqil
tZiiwmreM KS). Fedsiie,vciL. 56,m.
169, Tlgwt, 1991.
Ii] A.O. Freiez,P. Fadin, sdP.C. B.lhs§˜hrb
ml - vesim3.0. IrriEtT&˜˜-˜˜˜˜
Ol.mz, l4xdll996.
,,, birthday
fZl B.E;llisldardM.wMszgswwith
attacks .
MD5. FmLab' cQ@@&es,vcil.1m.1. s@irgl9%.
constitute the
a H. K?mc&,M. Bd.areadR.˜tti. IN!&*:
best known
Iccwd+Gfcar˜metial.mdraft
forgery attacks
ckaft-ti-etxt.00, kh?dll996.
against the
Pal P.mtzgeradW.sinpnn.˜˜tialusirg
HMAC con-
Keyed.MD5.IEFNebmrkbhkitgQtap,RFt31828,
StfLxtion. (. J
z4.gJst 1995.
Howevsr,
NR.&zkle.Chvayhs+hfm-ctiasdc˜˜.pdvances
for reasonable
incL3%mkw-c89˜,mmin
hash functions,
ccnplter ScierceVd.435,G.Bmssadd.,˜-
their practical
VdxL 1989. (Basedcnlxvlmbd˜ fran 1979
relevance is
cdhi.sEh.Dthssis,Simfmd, 1979).
negligible.
P2lB.FrmzelandP.vmCbrscht.˜˜x˜TaYibdd-
irgfastMxshhshKxeials. pdvancesti
CQTmlcgy-qpb95Pmsdirg,Lshlrsmesin
Caqmter Science Vol. 963, D. ath d,
3x+.Em-veclas, l9x
U31B.ArmzeladP.˜hdr%.ChU-esari˜ofbo
l?zc EdqzithrE.. Zibmzsinm-anocryP96
p!3mdws. LeaR-ehbtesinanprter˜˜,U.
Mauare3-, sgiqErG&g, 1996.
[3g3E.˜˜mdA.Shif˜.˜IheSeare&peYl'˜
Tm-sfk PL-daxil. Btex-& &aft cfbft-SW
ol.tz&, FfibEayl996.
tl5lR.Rhst.%hs˜˜˜˜˜h˜et-
work Workirgtrap, RFCl321, -1992.
rl6JFms1&0-1,salreHshsYzimhd Ftzthal Infmtial
PnxEssirg- mFs), m3liakn1˜1, Itaia-d
Insthteof˜ a-dTechtmlqy, US Dqxdnmt
of Comerce, WahirgtmD.C.,fpill995.
U7j G. Tsdik. M?ssags auihnticatim with a-rsey h&h
-. mofm'92.
˜P.vanOxzdmtadM.Wia-s.l?saUdUiUihmgtn&
tithzy&ilimtito˜Flrrtiasdnisaete˜-
K&s.Pmzdiq5of˜2dmanf.,orrplter˜
axmlldmb secmity, Ftlir&vA, bknAhT1994.


Eia
THE TECHNICAL NEWSLETTER OF RSA LABORATORIES - CRVPlOBY IES
S P I? I N G I996
Page 25
Previous Page Home Next Page
A N N 0 U N C E M E N T S


in this issue:
l Asymmetric


Encryptlon:
Evo/ution and
Enhancements
l PayWord and


MicroMint
l The HMAC


Construcfion




For contact and
distribution
inforrndion, see
page 2 of this
newslefter.




FIRST CLASS
U.S. POSTAGE




100 MARINE PARKWAY
REDWOOD CITY
CA. 94065-1031
T E L 415/595-7703
FAX 4151595.4126
rsa-labs@rsa.com
Page 26
Previous Page Home Next Page
VOLUME 1, NUMBER 3 - AUTUMN 1995


C˜˜˜˜˜B˜˜˜˜




The technical newsletter of RSA Laboratories, a division of RSA Data Security, Inc.
Contents




2
Editor™s h™ote

RSA for Paranoids
4
Algorithms Li@are

Adi Shamir whose encrypted messages should remain secret for
several decades, since it is almost impossible to pre-
Applied Math Department
dict the progress of factoring algorithms over such a
The Weizmann Institute of Science
long period of time. The only reasonable course of
Rehovot 76100, Israel
action is to use huge margins of safety, but this will
14
One of the most important decisions in practical make the RSA operations extremely slow.
Freqcently Asked
implementations of the RSA cryptosystem is the
Questions
All the known factoring algorithms can be divided
choice of modulus size. It is clear that the standard
size of 5 12 bits no longer provides adequate protec- into two broad types: algorithms whose running
time depends on the size of the factors, and algo-
tion, and should be substantially increased. How-
ever, the time complexity of modular exponentia- rithms whose running time depends only on the
size of the factored number n. The oldest factoring
tion grows rapidly with the size of the modulus,
algorithms typically searched for the smallest fac-
and thus it is difficult to choose a size which com-
bines efficient operation with long term security. tor p of n, and were thus of the first type. However,
modem algorithms tend to use indirect approaches
In this note we describe a new variant of the RSA
cryptosystem called “unbalanced RSA”, which which require the same time to find a single digit
makes it possible to increase the modulus size from or a fifty digit prime factor of n.
500 bits to 5,000 bits without any speed penalty.
The fastest factoring algorithm of the first type is
Conventional RSA currently the elliptic curve method. Its asymptotic
running time is exp(O((ln(p))“2* (lnln(p))“2)), but
The security of the RSA cryptosystem depends
(but is not provably equivalent to) the difficulty of its basic operations are very slow. The largest factor
ever found in practice with this algorithm was
factoring the modulus n, which is the product of
about 145 bits long (A. Lenstra, private communi-
two equal size primes p and 4. Until recently, the
cation), and it is very unlikely that this algorithm
minimum recommended size of n was 512 bits.
will be able to find the 256 bit factors of 512 bit
However, recent advances in factoring algorithms
make it necessary to increase this size. Since the RSA keys in the next few years.
time complexity of RSA computations is already
Factoring algorithms of the second type are much
substantial, and grows cubically with the size of the
faster, since they can use a wider array of math-
modulus, the new size should by necessity be a com-
ematical techniques. The best algorithm of this type
promise between efficiency and security. The choice
is currently the general number field sieve. It has
is particularly difficult for paranoid organizations
an asymptotic complexity of exp(O( (In(n))˜/, l



(lnln(n))“3)), and is believed to be capable of fac-

<<

. 5
( 19 .)



>>