RSA Hardware Implementation

By Cetin Kaya Koc

The RSA algorithm, invented by Rivest, Shamir, and Adleman [25], is one of the simplest public-key cryptosystems.

The RSA algorithm can be used to send encrypted messages and to produce digital signatures for electronic documents. It provides a procedure for signing a digital document, and verifying whether the signature is indeed authentic. The signing of a digital document is somewhat dierent from signing a paper document, where the same signature is being produced for all paper documents. A digital signature cannot be a constant; it is a function of the digital document for which it was produced. After the signature (which is just another piece of digital data) of a digital document is obtained, it is attached to the document for anyone wishing the verify the authenticity of the document and the signature. We refer the reader to the technical reports Answers to Frequently Asked Questions About Today's Cryptography and Public Key Cryptography Standards published by the RSA Laboratories [26, 27] for answers to certain questions on these issues.

Computation of Modular Exponentiation
Once the modulus and the private and public exponents are determined, the senders and recipients perform a single operation for signing, veri cation, encryption, and decryption. The operation required is the computation of Me (mod n), i.e., the modular exponentiation. The modular exponentiation operation is a common operation for scrambling; it is used in several cryptosystems. For example, the Diffie-Hellman key exchange scheme requires modular exponentiation [6]. Furthermore, the ElGamal signature scheme [7] and the Digital Signature Standard (DSS) of the National Institute for Standards and Technology [22] also require the computation of modular exponentiation. However, we note that the exponentiation process in a cryptosystem based on the discrete logarithm problem is slightly dierent: The base (M) and the modulus (n) are known in advance. This allows some precomputation since powers of the base can be precomputed and saved [5]. In the exponentiation process for the RSA algorithm, we know the exponent (e) and the modulus (n) in advance but not the base (M); thus, such optimizations are not likely to be applicable.

In the following sections we will review techniques for implementation of the modular exponentiation operation in hardware. We will study techniques for exponentiation, modular multiplication, modular addition, and addition operations. We intend to cover mathematical and algorithmic aspects of the modular exponentiation operation, providing the necessary knowledge to the hardware designer who is interested implementing the RSA algorithm using a particular technology. We draw our material from computer arithmetic books [32, 10, 34, 17], collection of articles [31, 30], and journal and conference articles on hardware structures for performing the modularmultiplication and exponentiations [24, 16, 28, 9, 4, 13, 14, 15, 33]. For implementing the RSA algorithm in software, we refer the reader to the companion report High-Speed RSA Implementation published by the RSA Laboratories [12].

Click to Download

Embedded, Everywhere: A Research Agenda For Networked Systems Of Embedded Computers

By Committee On Networked Systems Of Embedded Computers

Continued advances in information technologies are enabling a growing number of physical devices to be imbued with computing and communications capabilities. Aircraft, cars, household appliances, cellular telephones, and health monitoring devices all contain microprocessors that are being linked with other information processing devices. Such examples represent only the very beginning of what is possible. As microprocessors continue to shrink, wireless radios are also becoming more powerful and compact. As the cost of these and related technologies continues to decrease, computing and communications technologies will be embedded into everyday objects of all kinds to allow objects to sense and react to their changing environments. Networks comprising thousands or millions of sensors could monitor the environment, the battlefield, or the factory floor; smart spaces containing hundreds of smart surfaces and intelligent appliances could provide access to computational resources.

Getting to this point will not be easy. Networks of embedded computers pose a host of challenges qualitatively different from those faced by more traditional computers or stand-alone embedded computers because they will be more tightly integrated with their physical environments, more autonomous, and more constrained in terms of space, power, and other resources. They will also need to operate, communicate, and adapt in real time, often unattended. Enabling such innovation will require that a number of research challenges be overcome. How can large numbers of embedded computing devices assemble themselves seamlessly into an integrated network? How can their performance be guaranteed? How can social issues raised by the advent of more pervasive information collection and processing--for example, concerns about privacy, robustness, and usability--be addressed?

This report examines both issues related to components of embedded computers--such as hardware needs, operating systems, programming capabilities, and human interfaces--and systems-level issues resulting from the interconnection of multiple embedded computers--system architectures, coordination, adaptation, reliability, security, safety, interoperability, stability, and guaranteed performance. To that end, the committee attempted to answer questions such as the following:

• What are networked systems of embedded computing systems? How do networks of embedded computers differ from more traditional computer networks? How do these differences affect research needs?
• What types of applications could arise from greater networking of embedded systems?
• What are the general characteristics of different applications? What would be the benefits and capabilities of such systems?
• How can systems of interconnected embedded processors be more easily designed, developed, and maintained? How can system reliability, safety, operability, and maintainability be ensured in networked systems? How do such considerations differ for embedded and more traditional forms of computing?
• What kinds of advances are needed in enabling component technologies, such as hardware devices, operating systems, and communications networks, to make EmNets possible and more capable?
• What types of user interfaces are needed to allow users to interact with and to program systems composed of large numbers of interconnected embedded systems? How do these requirements differ for different kinds of users (experts, novices, system integrators)? What types of "programming" will consumers be expected to perform?
• How can the stability and effectiveness of interconnected systems of embedded computers be assured if individual components come from a wide variety of developers and use a variety of hardware and software platforms, some of which may run the latest versions of the software, and others of which may be several generations behind?

Click to Read More

Embedded Linux Distributions Quick Reference Guide

From linuxdevices.com

This Quick Reference Guide provides brief descriptions of many of the currently available commercial and non-commercial sources for Embedded Linux distributions and implementations, and includes pointers to more detailed information. We sincerely hope this guide will assist you in locating Linux-based solutions that match your system requirements.

This quick reference guide is organized in four parts . . .

• Part 1: Introduction and Overview to this Guide -- you are reading it now.
• Part 2: Embedded Linux Commercial Distributions -- these are Embedded Linux distributions that are maintained and supported by companies as commercial products. They offer a wide range of capabililties and target a broad assortment of markets, from high-end telecommunications infrastructure, to handheld computers, to "deeply embedded" data acquisition and control.
• Part 3: Open Source Embedded Linux Implementations -- the Embedded Linux implementations in this category are available as downloadable object and source code, and are covered by open source licenses.
• Part 4: Recommended further reading -- here, we provide a "recommended reading list" of selected LinuxDevices.com articles and whitepapers that provide additional information about Embedded Linux distributions, techniques, and technologies.

Click to Read More

Elliptic Curve Cryptosystems on Reconfigurable Hardware

by Martin Christopher Rosner

Security issues will play an important role in the majority of communication and computer networks of the future. As the Internet becomes more and more accessible to the public, security measures will have to be strengthened. Elliptic curve cryptosystems allow for shorter operand lengths than other public-key schemes based on the discrete logarithm in nite elds and the integer factorization problem and are thus attractive for many applications.

This thesis describes an implementation of a crypto engine based on elliptic curves. The underlying algebraic structures are composite Galois fields GF((2n)m) in a standard base representation. As a major new feature, the system is developed for a recon gurable platform based on Field Programmable Gate Arrays (FPGAs). FPGAs combine the flexibility of software solutions with the security of traditional hardware implementations. In particular, it is possible to easily change all algorithm parameters such as curve coefficients, field order, or field representation.

The thesis deals with the design and implementation of elliptic curve point multiplication architectures. The architectures are described in VHDL and mapped to Xilinx FPGA devices. Architectures over Galois fields of dierent order and representation were implemented and compared. Area and timing measurements are provided for all architectures. It is shown that a full point multiplication on elliptic curves of real-world size can be implemented on commercially available FPGAs.

Click to Download

Attacks on Cryptoprocessor Transaction Sets

By Mike Bond

Attacks are presented on the IBM 4758 CCA and the Visa Security Module. Two new attack principles are demonstrated. Related key attacks use known or chosen differences between two cryptographic keys. Data protected with one key can then be abused by manipulation using the other key. Meet in the middle attacks work by generating a large number of unknown keys of the same type, thus reducing the key space that must be searched to discover the value of one of the keys in the type. Design heuristics are presented to avoid these attacks and other common errors.

A cryptoprocessor is a tamper-resistant processor designed to manage cryptographic keys and data in high-risk situations. The concept of a cryptoprocessor arose because conventional operating systems are too bug-ridden and computers too physically insecure to be trusted with information of high value. A normal microprocessor is enclosed within a tamper-resistant environment, so that sensitive information can only be altered or released through a tightly defined software interface – a transaction set. In combination with access control, the transaction set should prevent abuse of the sensitive information. However, as the functionality and flexibility of transaction sets have been pushed up by manufacturers and clients, this extra complexity has made bugs in transaction sets inevitable.

Sections 2 and 3 of this paper give an overview of cryptoprocessors in the context of four important architectural principles, and then describe the new vulnerabilities in a generalised way. Sections 4 and 5 introduce attacks on two widely fielded cryptoprocessors – the IBM 4758, and the Visa Security Module. Finally, some straightforward design heuristics are suggested that, whilst not guaranteeing the security of a transaction set, will at least stop the same mistakes being made over again.

Click to Download

ABCs of System Programming Volume 5 - OS/390

This redbook is Volume 5 of a five-volume set that is designed to introduce the structure of an OS/390 and S/390 operating environment. The set will help you install, tailor, and configure an OS/390 operating system, and is intended for system programmers who are new to an OS/390 environment.

In this Volume, Chapter 1 provides an description of a base and Parallel Sysplex. A sysplex is a collection of OS/390 systems that cooperate, using certain hardware and software products, to process work.

Chapter 2 describes the MVS System Logger. System logger is a set of services that allows an application to write, browse, and delete log data. You can use system logger services to merge data from multiple instances of an application, including merging data from different systems across a sysplex.

Chapter 3 describes Global resource serialization (GRS) which offers the control needed to ensure the integrity of resources in a multisystem environment. Combining the systems that access shared resources into a global resource serialization complex enables you to serialize resourcesacross multiple systems.

Chapter 4 describes the operation of an MVS system which involves console operations or how operators interact with MVS to monitor or control the hardware and software and message and command processing that forms the basis of operator interaction with MVS and the basis of MVS automation.

Chapter 5 describes Automatic Restart Management (ARM) which is the key to automating the restarting of subsystems and applications (referred to collectively as applications) so they can recover work they were doing at the time of an application or system failure and release resources, such as locks, that they were holding. With an automatic restart management policy, you can optionally control the way restarts are done.

Chapter 6 describes the hardware management console (HMC) which provides a single point of control to manage your central processor complex (CPC).

Chapter 7 describes workload management which provides a way to define MVS externals and tune MVS without having to specify low-level parameters. The focus is on setting performance goals for work, and letting the Workload Manager handle processing to meet the goals.

Chapter 8 describes problem diagnosis. MVS supplies many tools and service aids that assist with problem diagnosis. These tools includes dumps and traces, while service aids includes the other facilities provided for diagnosis.

Click to Download