1999 CHES嵌入式安全会议论文精华

需积分: 34 16 浏览量更新于2024-07-20 收藏 4.59MB PDF 举报

CHES1999论文是嵌入式安全领域的一项重要研究成果，发表在1999年的顶级会议——计算机硬件与嵌入式安全大会（CHES）上。该论文集展示了当时在嵌入式系统中的安全技术研究前沿，特别关注了如何确保这些系统在有限资源和高度受限环境下，如移动设备、智能卡和物联网设备的安全性。嵌入式安全是一个关键领域，它涉及将安全措施集成到小型、低功耗设备中，以防止未经授权的访问、数据泄露和恶意攻击。CHES作为国际学术界的盛会，汇集了来自全球的研究者们，他们共同探讨最新的加密算法、安全架构设计、硬件安全实现以及嵌入式系统的安全性挑战。 1999年的CHES论文库可能包含对公钥加密技术（如欧密会Eurocrypt、美密会Crypto、亚密会Asiacrypt等）的深入分析和应用研究，这些都是密码学领域的重要组成部分，对于保护数据隐私、网络安全和设备认证等方面有着显著影响。论文可能探讨了如哈希函数、消息认证码、数字签名、密钥管理和侧信道攻击等关键技术及其在嵌入式环境中的优化策略。此外，论文可能还涵盖了如何通过硬件级别的安全增强，比如专用集成电路（ASIC）、现场可编程门阵列（FPGA）或特定安全模块，来提升设备的安全性能。在资源有限的嵌入式设备上，效率和安全性之间的平衡是研究的核心问题。山东大学数学院的信息安全专业在此领域的研究实力不容小觑，他们的研究生团队活跃于CHES论文库，反映了他们在密码学和网络安全方面的深厚底蕴。论文库中的4000余篇论文不仅是学术成果的展示，也为该领域的发展提供了丰富的参考资源。参与CHES的论文讨论有助于参与者了解行业动态，发现新的安全威胁和解决方案，同时也推动了嵌入式安全技术的进步。对于从事密码学或网络安全学习和研究的人来说，CHES1999论文集是一个宝贵的资料来源，可以帮助他们深化理论理解，提升实践能力。数缘社区提供的电子书库和数学综合讨论区则为学习者提供了一个交流和分享知识的平台，使大家能够共同进步。

4 A. Shamir

2 The QS Factoring Algorithm

Given the RSA number n = pq, the QS algorithm tries to construct two numbers

y and z such that y 6= ±z (mod n) and y

= z

(mod n). Knowledge of such

a pair makes it easy to factor n since gcd(y − z, n) is either p or q.Toﬁnd

such y and z, we generate a large number of values y

,...,y

, compute

each y

(mod n), and try to factor it into a product of primes p

from a prime

base B consisting of the k smallest primes p

=2,p

=3,...,p

. Numbers

(mod n) which have such factorizations into

j=1

are called smooth.If

the number of smooth modular squares found in such a way exceeds k,wecan

use Gauss elimination to ﬁnd a subset of the vectors ( e

,...,e

) of the prime

multiplicities which is linearly dependent modulo 2. When the corresponding

(mod n) and their factorizations are multiplied, we get an equation of the

form

i=1

)

j=1

(mod n) where all the b

’s (which deﬁne the subset)

are 0’s and 1’s and all the c

’s (which are the sums of the prime multiplicities)

are even numbers. We can now get the desired equation y

= z

( mod n)by

deﬁning y =

i=1

(mod n) and z =

j=1

(mod n).

The key to the eﬃciency of the QS algorithm is the generation of many

small modular squares whose smoothness is easy to test. Consider the simplest

case in which we use the quadratic polynomial f (x)=(a + x)

(mod n) where

a = b

(n)c, and choose y

= a + i for i =1, 2,...,m. Then it is easy to see that

for small m the corresponding y

= f (i)(mod n) are half size modular squares

which are much more likely to be smooth numbers than random modular squares.

The simplest way of testing the smoothness of the values in such a sequence

is to perform trial division of each value in the sequence by each prime in the

basis. Since the f(i)’s are hundreds of bits long, this is very slow.

The QS algorithm expresses all the generated f(1),...,f(m) in the non mo-

dular form f(i)=(a + i)

−n (since m is small), and determines which of these

values are divisible by p

from the basis B by solving the quadratic modular

equation (a + i)

− n =0(mod p

). This is easy, since the modulus p

is quite

small.

The quadratic equation mod p

will have either zero or two solutions d

and

”. In the ﬁrst case we can deduce that none of the f (i)’s will be divisible by

, and in the second case we can deduce that f(i) will be divisible by p

if and

only if i belongs to the union of the two arithmetic progressions p

∗ r + d

and

∗ r + d

” for r ≥ 0.

The smoothness test in the QS algorithm is based on an array A of m coun-

ters, where the i −th entry is associated with f(i). The sieving algorithm zeroes

all these counters, and then loops over the primes in the basis. For each prime p

and for each one of its two arithmetic progressions (if they exist), the algorithm

scans the counter array, and adds the constant log

) to all the counters A(i)

We ignore the issue of the divisibility of f(i) by higher powers of p

, since except

for the smallest primes in the basis this is extremely unlikely, and we can explicitly

add the powers of the ﬁrst few primes to the basis without substantially increasing

its size.

Factoring Large Numbers with the TWINKLE Device 5

whose indices i belong to the arithmetic progression (there are about m/p

such

indices). At the end of this loop, the value of A(i) describes the (approximate)

binary length of the largest divisor of f(i) which factors completely over the

prime base B. The algorithm then scans the array, ﬁnds all the entries i for

which A(i) is close to the binary length of f (i), tests that these f(i)’s are indeed

smooth by trial division, and uses them in order to factor n.

Typical large scale factoring attacks with networks of PC’s may use m =

100, 000, 000 and k = 200, 000. The array requires 100 megabytes of RAM, and

its counters can be accessed at the standard bus speed of 100 megahertz.

Just

scanning such a huge array requires about one second. Well optimized implemen-

tations of the QS algorithm perform the sieving in 5 to 10 seconds, and ﬁnd very

few smooth numbers. They then choose a diﬀerent quadratic polynomial f

(x),

and repeat the sieving run (on the same machine, or on a diﬀerent machine wor-

king in parallel). This phase stops when a total of k + 1 smooth modular squares

are collected in all the sieving runs, and a single powerful computer performs

the Gauss elimination algorithm and the actual factorization in a small fraction

of the time which was devoted to the sieving.

In the next section we describe the new TWINKLE device, which is an ul-

trafast optical siever. It costs about the same as a powerful PC or a workstation,

but can test the smoothness of 100,000,000 modular squares over a prime base

of 200,000 primes in less than 0.01 seconds. This is 500 to 1000 times faster than

the conventional sieving approach described above.

3 The TWINKLE Device

The TWINKLE device is a simple optoelectronic device which is housed in an

opaque blackened cylinder whose diameter is about 6 inches and whose height

is about 10 inches. The bottom of the cylinder consists of a large collection of

LEDs (light emitting diodes) which twinkle at various frequencies, and the top

of the cylinder contains a photodetector which measures the total amount of

light emitted at any given moment by all the LEDs. The photodetector alerts a

connected PC whenever this total exceeds a certain threshold. Such events are

related to the detection of possibly smooth numbers, and their precise timing is

the only output of the TWINKLE device. Since these events are extremely rare,

the PC can leisurely translate the timing of each reported event to a candidate

modular square, verify its smoothness via trial division, and use it in a conven-

tional implementation of the QS or NFS algorithms in order to factor the input

The standard PC implementation of the sieving technique assigns modular

squares to array elements (using space) and loops over the primes (using time).

The TWINKLE device assigns primes to LEDs (using space) and loops over the

Note that the faster cache memory is of little use, since the sieving process accesses

arithmetic progressions of addresses with huge jumps, which create continuous cache

misses.

Factoring Large Numbers with the TWINKLE Device 7

intensity measurement is likely to be inﬂuenced by many sources of errors. For

example, the grey levels of the ﬁlter are only approximations of the logs, and

even uniformly designed LEDs may have actual intensities varying by 20% or

more. We can improve the accuracy of the TWINKLE device by measuring the

actual ﬁltered intensity of each LED in the manufactured array, and assigning

the sequence of primes to the various LEDs based on their sorted list of measured

intensities. However, the QS and NFS factoring algorithms are very forgiving to

such measurement errors, and in PC implementations they use crude integer

approximations to the logs in order to speed up the computation. There are two

possible types of errors: missed events and false alarms. To minimize the number

of missed events we can set a slightly lower reporting threshold, and to eliminate

the resultant false alarms we can later test all the reported events on a PC, in

order to ﬁnd the extremely rare real events among the rare false alarms. For

typical values of the parameters, the average binary size of the smooth part of

candidate values is about one tenth of their size, and only a tiny fraction of all

candidate values have ratios exceeding one half. As a result, the desired events

stand out very clearly as isolated narrow peaks which are about ten times higher

than the background noise.

We claim that optical sieving is much better than conventional counter array

sieving for the following reasons:

1. We can perform optical sieving at an extremely fast clock rate. Typical si-

licon RAM chips in standard PC’s operate at about 100 megahertz. LEDs,

on the other hand, are manufactured with a much faster Gallium Arsenide

(GaAs) technology, and can be clocked at rates exceeding 10 gigahertz with-

out diﬃculty. Commercially available LEDs and photodetectors are used to

send 10 gigabits per second along ﬁber optic cables, and GaAs devices are

widely used at similar clock rates as routers in high speed networks.

2. We can instantaneously add hundreds of thousands of optical contributions,

if we do not need perfect accuracy. Building a digital adder with 200,000

inputs which computes their sum in a single clock cycle is completely unrea-

listic.

3. The optical technique does not need huge arrays of counters. Instead of using

one memory cell per sieved value, we use one time slice per sieved value. Even

with the declining cost of fast memories, time is cheaper than space.

4. In the optical technique do not have to scan the array at the beginning in

order to zero it, and do not have to scan the array again at the end in order

to ﬁnd its high entries - both operations are done at no extra cost during

the actual sieving.

In the remaining sections we ﬂesh out the design of each cell and the archi-

tecture of the whole device. We based this design on many conversations with

experienced GaAs chip designers, and used only commercially available tech-

nologies. We may be oﬀ by a small factor in some of our size speed and cost

estimates, but we believe that the design is realistic, and that someone will try

it out in the near future.

剩余363页未读，继续阅读

vodkazc

粉丝: 0
资源: 1

1999 CHES嵌入式安全会议论文精华

CHES会议论文：LED分组密码设计完整解析

matlab加密代码-randomdelays-traces:来自CHES论文的关于随机延迟的数据集

led-full_ches会议_LEDblockcipher_full_

论文研究-分组密码PRESENT算法基于MILP的分析.pdf

论文研究-轻量级分组密码SIMECK多路径不可能差分攻击 .pdf

CHES-FY系统织物弯曲性能参数优化关键影响因素

CHES-FY系统在织物硬挺风格聚类分析中的应用

CHES-FY系统下的织物弯曲性能理论建模与测试分析

CHES-FY系统：单次测试综合表征织物性能的有效工具

停车场管理系统c语言.docx

最新资源