Power dissipation has become one of the major limiting factors in the design of digital ASICs. Low power dissipation will increase the mobility of the ASIC by reducing the system cost, size and weight. DSP blocks are a major source of power dissipation in modern ASICs. The residue number system (RNS) has, for a long time, been proposed as an alternative to the regular two's complement number system (TCS) in DSP applications to reduce the power dissipation. The basic concept of RNS is to first encode the input data into several smaller independent residues. The computational operations are then performed in parallel and the results are eventually decoded back to the original number system. Due to the inherent parallelism of the residue arithmetics, hardware implementation results in multiple smaller design units. Therefore an RNS design requires low leakage power cells and will result in a lower switching activity. The residue number system has been analyzed by first investigating different implementations of RNS adders and multipliers (which are the basic arithmetic functions in a DSP system) and then deriving an optimal combination of these. The optimum combinations have been used to implement an FIR filter in RNS that has been compared with a TCS FIR filter. By providing different input data and coefficients to both the RNS and TCS FIR filter an evaluation of their respective performance in terms of area, power and operating frequency have been performed. The result is promising for uniform distributed random input data with approximately 15 % reduction of average power with RNS compared to TCS. For a realistic DSP application with normally distributed input data, the power reduction is negligible for practical purposes.

Master of Science / Department of Electrical and Computer Engineering / Balasubramaniam Natarajan / Space-time coding (STC) schemes for Multiple Input Multiple Output (MIMO) systems have been an area of active research in the past decade. In this thesis, we propose a novel design of Space-Time Block Codes (STBCs) using Redundant Residue Number System (RRNS) codes, which are ideal for high data rate communication systems. Application of RRNS as a concatenated STC scheme to a MIMO wireless communication system is the main motivation for this work. We have optimized the link between residues and complex constellations by incorporating the “Direct Mapping” scheme, where residues are mapped directly to Gray coded constellations. Knowledge of apriori probabilities of residues is utilized to implement a probability based “Distance-Aware Direct Mapping” (DA) scheme, which uses a set-partitioning approach to map the most probable residues such that they are separated by the maximum possible distance. We have proposed an “Indirect Mapping” scheme, where we convert the residues back to bits before mapping them. We have also proposed an adaptive demapping scheme which utilizes the RRNS code structure to reduce the ML decoding complexity and improve the error performance. We quantify the upper bounds on codeword and bit error probabilities of both Systematic and Non-systematic RRNS-STBC and characterize the achievable coding and diversity gains assuming maximum likelihood decoding (MLD). Simulation results demonstrate that the DA Mapping scheme provides performance gain relative to a Gray coded direct mapping scheme. We show that Systematic RRNS-STBC codes provide superior performance compared to Nonsystematic RRNS-STBC, for the same code parameters, owing to more efficient binary to residue mapping. When compared to other concatenated STBC and Orthogonal STBC (OSTBC) schemes, the proposed system gives better performance at low SNRs.

This doctoral thesis approaches the problem of designing versatile architectures for cryptographic hardware. By the term versatile we define hardware architectures capable of supporting a variety of arithmetic operations and algorithms useful in cryptography, with no need to reconfigure the internal interconnections of the integrated circuit. A versatile architecture could offer considerable benefits to the end-user. By embedding a variety of crucial operations in a common architecture, the user is able to switch seamlessly the underlying cryptographic protocols, which not only gives an added value in the design from flexibility but also from practicality point of view. The total cost of a cryptographic application can be also benefited; assuming a versatile integrated circuit which requires no additional circuitry for other vital operations (for example input–output converters) it is easy to deduce that the total cost of development and fabrication of these extra components is eliminated, thus reducing the total production cost. We follow a systematic approach for developing and presenting the proposed versatile architectures. First, an in-depth analysis of the algorithms of interest is carried out, in order to identify new research areas and weaknesses of existing solutions. The proposed algorithms and architectures operate on Galois Fields GF of the form GF(p) for integers and GF(2^n) for polynomials. Alternative number representation systems such as Residue Number System (RNS) for integers and Polynomial Residue Number System (PRNS) for polynomials are employed. The mathematical validity of the proposed algorithms and the applicability of RNS and PRNS in the context of cryptographic algorithms is also presented. The derived algorithms are decomposed in a way that versatile structures can be formulated and the corresponding hardware is developed and evaluated. New cryptanalytic properties of the proposed algorithms against certain types of attacks are also highlighted. Furthermore, we try to approach a fundamental problem in Very Large Scale Integration (VLSI) design, that is the problem of evaluating and comparing architectures using models independent from the underlying fabrication technology. We also provide generic methods to evaluate the optimal operation parameters of the proposed architectures and methods to optimize the proposed architectures in terms of speed, area, and area x speed product, based on the needs of the underlying application. The proposed methodologies can be expanded to include applications other than cryptography. Finally, novel algorithms based on new mathematical and design problems for the crucial operation of modular multiplication are presented. The new algorithms preserve the versatile characteristics discussed previously and it is proved that, along with existing algorithms in the literature, they may forma large family of algorithms applicable in cryptography, unified under the common frame of the proposed versatile architectures. / Η παρούσα διατριβή άπτεται του θέματος της ανάπτυξης ευέλικτων αρχιτεκτονικών κρυπτογραφίας σε ολοκληρωμένα κυκλώματα υψηλής ολοκλήρωσης (VLSI). Με τον όρο ευέλικτες ορίζονται οι αρχιτεκτονικές που δύνανται να υλοποιούν πλήθος βασικών αριθμητικών πράξεων για την εκτέλεση κρυπτογραφικών αλγορίθμων, χωρίς την ανάγκη επαναπροσδιορισμού των εσωτερικών διατάξεων στο ολοκληρωμένο κύκλωμα. Η χρήση ευέλικτων αρχιτεκτονικών παρέχει πολλαπλά οφέλη στο χρήστη. Η ενσωμάτωση κρίσιμων πράξεων απαραίτητων στη κρυπτογραφία σε μια κοινή αρχιτεκτονική δίνει τη δυνατότητα στο χρήστη να εναλλάσσει το υποστηριζόμενο κρυπτογραφικό πρωτόκολλο, εισάγοντας έτσι χαρακτηριστικά ευελιξίας και πρακτικότητας, χωρίς επιπρόσθετη επιβάρυνση του συστήματος σε υλικό. Αξίζει να σημειωθεί πως οι εναλλαγές αυτές δεν απαιτούν τη παρέμβαση του χρήστη. Σημαντική είναι η συνεισφορά μιας ευέλικτης αρχιτεκτονικής και στο κόστος μιας εφαρμογής. Αναλογιζόμενοι ένα ολοκληρωμένο κύκλωμα που μπορεί να υλοποιεί αυτόνομα όλες τις απαραίτητες πράξεις ενός αλγόριθμου χωρίς την εξάρτηση από εξωτερικά υποσυστήματα (π.χ. μετατροπείς εισόδου–εξόδου), είναι εύκολο να αντιληφθούμε πως το τελικό κόστος της εκάστοτε εφαρμογής μειώνεται σημαντικά καθώς μειώνονται οι ανάγκες υλοποίησης και διασύνδεσης επιπρόσθετων υποσυστημάτων στο ολοκληρωμένο κύκλωμα. Η ανάπτυξη των προτεινόμενων αρχιτεκτονικών ακολουθεί μια δομημένη προσέγγιση. Διενεργείται εκτενής μελέτη για τον προσδιορισμό γόνιμων ερευνητικών περιοχών και εντοπίζονται προβλήματα και δυνατότητες βελτιστοποίησης υπαρχουσών κρυπτογραφικών λύσεων. Οι νέοι αλγόριθμοι που αναπτύσσονται αφορούν τα Galois πεδία GF(p) και GF(2^n) και χρησιμοποιούν εναλλακτικές αριθμητικές αναπαράστασης δεδομένων όπως το αριθμητικό σύστημα υπολοίπων (Residue Number System (RNS)) για ακέραιους αριθμούς και το πολυωνυμικό αριθμητικό σύστημα υπολοίπων (Polynomial Residue Number System (PRNS)) για πολυώνυμα. Αποδεικνύεται η μαθηματική τους ορθότητα και βελτιστοποιούνται κατά τέτοιο τρόπο ώστε να σχηματίζουν ευέλικτες δομές. Αναπτύσσεται το κατάλληλο υλικό (hardware) και διενεργείται μελέτη χρήσιμων ιδιοτήτων των νέων αλγορίθμων, όπως για παράδειγμα νέες κρυπταναλυτικές ιδιότητες. Επιπρόσθετα, προσεγγίζουμε στα πλαίσια της διατριβής ένα βασικό πρόβλημα της επιστήμης σχεδιασμού ολοκληρωμένων συστημάτων μεγάλης κλίμακας (Very Large Scale Integration (VLSI)). Συγκεκριμένα, προτείνονται μέθοδοι σύγκρισης αρχιτεκτονικών ανεξαρτήτως τεχνολογίας καθώς και τρόποι εύρεσης των βέλτιστων συνθηκών λειτουργίας των προτεινόμενων αρχιτεκτονικών. Οι μέθοδοι αυτές επιτρέπουν στον σχεδιαστή να παραμετροποιήσει τις προτεινόμενες αρχιτεκτονικές με βάση τη ταχύτητα, επιφάνεια, ή το γινόμενο ταχύτητα x επιφάνεια. Οι προτεινόμενες μεθοδολογίες μπορούν εύκολα να επεκταθούν και σε άλλες εφαρμογές πέραν της κρυπτογραφίας. Τέλος, προτείνονται νέοι αλγόριθμοι για τη σημαντικότατη για την κρυπτογραφία πράξη του πολλαπλασιασμού με υπόλοιπα. Οι νέοι αλγόριθμοι ενσωματώνουν από τη μία τις ιδέες των ευέλικτων δομών, από την άλλη όμως βασίζονται σε νέες ιδέες και μαθηματικά προβλήματα τα οποία προσπαθούμε να προσεγγίσουμε και να επιλύσουμε. Αποδεικνύεται πως είναι δυνατή η ενοποίηση μιας μεγάλης οικογένειας αλγορίθμων για χρήση στην κρυπτογραφία, υπό τη στέγη των προτεινόμενων μεθοδολογιών για ευέλικτο σχεδιασμό.

Este trabalho mostra os diversos sistemas de representação numérica, incluindo o sistema numérico normalmente utilizado em circuitos e alguns sistemas alternativos. Uma maior ênfase é dada ao sistema numérico por resíduos. Este último apresenta características muito interessantes para o desenvolvimento de circuitos aritméticos nos dias atuais, como por exemplo, a alta paralelização. São estudadas também as principais arquiteturas de somadores e multiplicadores. Várias descrições de circuitos aritméticos são feitas e sintetizadas. A arquitetura de circuitos aritméticos utilizando o sistema numérico por resíduos também é estudada e implementada. Os dados da síntese destes circuitos são comparados com os dados dos circuitos aritméticos tradicionais. Com isto, é possível avaliar as potenciais vantagens de se utilizar o sistema numérico por resíduos no desenvolvimento de circuitos aritméticos. / This work shows various numerical representation systems, including the system normally used in current circuits and some alternative systems. A great emphasis is given to the residue number system. This last one presents very interesting characteristics for the development of arithmetic circuits nowadays, as for example, the high parallelization. The main architectures of adders and multipliers are also studied. Some descriptions of arithmetic circuits are made and synthesized. The architecture of arithmetic circuits using the residue number system is also studied and implemented. The synthesis data of these circuits are compared with the traditional arithmetic circuits results. Then it is possible to evaluate the potential advantages of using the residue number system in arithmetic circuits development.

Este trabalho mostra os diversos sistemas de representação numérica, incluindo o sistema numérico normalmente utilizado em circuitos e alguns sistemas alternativos. Uma maior ênfase é dada ao sistema numérico por resíduos. Este último apresenta características muito interessantes para o desenvolvimento de circuitos aritméticos nos dias atuais, como por exemplo, a alta paralelização. São estudadas também as principais arquiteturas de somadores e multiplicadores. Várias descrições de circuitos aritméticos são feitas e sintetizadas. A arquitetura de circuitos aritméticos utilizando o sistema numérico por resíduos também é estudada e implementada. Os dados da síntese destes circuitos são comparados com os dados dos circuitos aritméticos tradicionais. Com isto, é possível avaliar as potenciais vantagens de se utilizar o sistema numérico por resíduos no desenvolvimento de circuitos aritméticos. / This work shows various numerical representation systems, including the system normally used in current circuits and some alternative systems. A great emphasis is given to the residue number system. This last one presents very interesting characteristics for the development of arithmetic circuits nowadays, as for example, the high parallelization. The main architectures of adders and multipliers are also studied. Some descriptions of arithmetic circuits are made and synthesized. The architecture of arithmetic circuits using the residue number system is also studied and implemented. The synthesis data of these circuits are compared with the traditional arithmetic circuits results. Then it is possible to evaluate the potential advantages of using the residue number system in arithmetic circuits development.

Este trabalho mostra os diversos sistemas de representação numérica, incluindo o sistema numérico normalmente utilizado em circuitos e alguns sistemas alternativos. Uma maior ênfase é dada ao sistema numérico por resíduos. Este último apresenta características muito interessantes para o desenvolvimento de circuitos aritméticos nos dias atuais, como por exemplo, a alta paralelização. São estudadas também as principais arquiteturas de somadores e multiplicadores. Várias descrições de circuitos aritméticos são feitas e sintetizadas. A arquitetura de circuitos aritméticos utilizando o sistema numérico por resíduos também é estudada e implementada. Os dados da síntese destes circuitos são comparados com os dados dos circuitos aritméticos tradicionais. Com isto, é possível avaliar as potenciais vantagens de se utilizar o sistema numérico por resíduos no desenvolvimento de circuitos aritméticos. / This work shows various numerical representation systems, including the system normally used in current circuits and some alternative systems. A great emphasis is given to the residue number system. This last one presents very interesting characteristics for the development of arithmetic circuits nowadays, as for example, the high parallelization. The main architectures of adders and multipliers are also studied. Some descriptions of arithmetic circuits are made and synthesized. The architecture of arithmetic circuits using the residue number system is also studied and implemented. The synthesis data of these circuits are compared with the traditional arithmetic circuits results. Then it is possible to evaluate the potential advantages of using the residue number system in arithmetic circuits development.

Internet-of-Things (IoT) devices are increasing in popularity due to their ability to help automate many aspects of daily life while performing these necessary duties on billions of low-power appliances. However, the perks of these small devices also come with additional constraints to security. Security always has been an issue with the rise of cryptographic backdoors and hackers reverse engineering the security protocols within devices to reveal the original state that was encrypted. Security researchers have done much work to prevent attacks with high power algorithms, such as the international effort to develop the current Advanced Encryption Standard (AES). Unfortunately, IoT devices do not typically have the computational resources to implement high-power algorithms such as AES, and must rely on lightweight primitives such as pseudorandom number generators, or PRNGs.This thesis explores the effectiveness, functionality, and use of PRNGs in different applications. First, this thesis investigates the confidentiality of a single-stage residue number system PRNG, which has previously been shown to provide extremely high quality outputs for simulation and digital communication applications when evaluated through traditional techniques like the battery of statistical tests used in the NIST Random Number Generation and DIEHARD test suites or in using Shannon entropy metrics. In contrast, rather than blindly performing statistical analyses on the outputs of the single-stage RNS PRNG, this thesis provides both white box and black box analyses that facilitate reverse engineering of the underlying RNS number generation algorithm to obtain the residues, or equivalently the key, of the RNS algorithm. This thesis develops and demonstrate a conditional entropy analysis that permits extraction of the key given a priori knowledge of state transitions as well as reverse engineering of the RNS PRNG algorithm and parameters (but not the key) in problems where the multiplicative RNS characteristic is too large to obtain a priori state transitions. This thesis then discusses multiple defenses and perturbations for the RNS system that defeat the original attack algorithm, including deliberate noise injection and code hopping. We present a modification to the algorithm that accounts for deliberate noise, but rapidly increases the search space and complexity. Lastly, a comparison of memory requirements and time required for the attacker and defender to maintain these defenses is presented. The next application of PRNGs is in building a translation for binary PRNGs to non-binary uses like card shuffling in a casino. This thesis explores a shuffler algorithm that utilizes RNS in Fisher-Yates shuffles, and that calls for inputs from any PRNG. Entropy is lost through this algorithm by the use of PRNG in lieu of TRNG and by its RNS component: a surjective mapping from a large domain of size $2^J$ to a substantially smaller set of arbitrary size $n$. Previous research on the specific RNS mapping process had developed a lower bound on the Shannon entropy loss from such a mapping, but this bound eliminates the mixed-radix component of the original formulation. This thesis calculates a more precise formula which takes into account the radix, $n$. This formulation is later used to specify the optimal parameters to simulate the shuffler with different test PRNGs. After implementing the shuffler with PRNGs with varying output entropies, the thesis examines the output value frequencies to discuss if utilizing PRNG is a feasible alternative for casinos to the higher-cost TRNG. / Master of Science / Cryptography, or the encrypting of data, has drawn widespread interest for years, initially sparking public concern through headlines and dramatized reenactments of hackers targeting security protocols. Previous cryptographic research commonly focused on developing the quickest, most secure ways to encrypt information on high-power computers. However, as wireless low-power devices such as smart home, security sensors, and learning thermostats gain popularity in ordinary life, interest is rising in protecting information being sent between devices that don't necessarily have the power and capabilities as those in a government facility. Lightweight primitives, the algorithms used to encrypt information between low-power devices, are one solution to this concern, though they are more susceptible to attackers who wish to reverse engineer the encrypting process. The pesudorandom number generator (PRNG) is a type of lightweight primitive that generates numbers that are essentially random even though it is possible to determine the input value, or seed, from the resulting output values. This thesis explores the effectiveness and functionality of PRNGs in different applications. First, this thesis explores a PRNG that has passed many statistical tests to prove its output values are random enough for certain applications. This project analyzes the quality of this PRNG through a new lens: its resistance to reverse engineering attacks. The thesis describes and implements an attack on the PRNG that allows an individual to reverse engineer the initial seed. The thesis then changes perspective from attacker to designer and develop defenses to this attack: by slightly modifying the algorithm, the designer can ensure that the reverse engineering process is so complex, time-consuming, and memory-requiring that implementing such an attack would be impractical for an attacker. The next application of PRNGs is in the casino industry, in which low-power and cost-effective automatic card shufflers for games like poker are becoming popular. This thesis explores a solution for optimal shuffling of a deck of cards.

Internet-of-Things (IoT) devices have become increasingly popular in the last 10 years, yet also show an acceptance for lack of security due to hardware constraints. The range of sophistication in IoT devices varies substantially depending on the functionality required, so security options need to be flexible. Manufacturers typically either use no security, or lean towards the use of the Advanced Encryption Standard (AES) with a 128-bit key. AES-128 is suitable for the higher end of that IoT device range, but is costly enough in terms of memory, time, and energy consumption that some devices opt to use no security. Short development and a strong drive to market also contribute to a lack in security. Recent work in lightweight cryptography has analyzed the suitability of custom protocols using AES as a comparative baseline. AES outperforms most custom protocols when looking at security, but those analyses fail to take into account block size and future capabilities such as quantum computers. This thesis analyzes lightweight cryptographic primitives that would be suitable for use in IoT devices, helping fill a gap for "good enough" security within the size, weight, and power (SWaP) constraints common to IoT devices. The primitives have not undergone comprehensive cryptanalysis and this thesis attempts to provide a preliminary analysis of confidentiality. The first is a single-stage residue number system (RNS) pseudorandom number generator (PRNG) that was shown in previous publications to produce strong outputs when analyzed with statistical tests like the NIST RNG test suite and DIEHARD. However, through analysis, an intelligent multi-stage conditional probability attack based on the pigeonhole principle was devised to reverse engineer the initial state (key) of a single-stage RNS PRNG. The reverse engineering algorithm is presented and used against an IoT-caliber device to showcase the ability of an attacker to retrieve the initial state. Following, defenses based on intentional noise, time hopping, and code hopping are proposed. Further computation and memory analysis show the proposed defenses are simple in implementation, but increase complexity for an attacker to the point where reverse engineering the PRNG is likely no longer viable. The next primitive proposed is a block cipher combination technique based on Galois Extension Field multiplication. Using any PRNG to produce the pseudorandom stream, the block cipher combination technique generates a variable sized key matrix to encrypt plaintext. Electronic Codebook (ECB) and Cipher Feedback (CFB) modes of operation are discussed. Both system modes are implemented in MATLAB as well as on a Texas Instruments (TI) MSP430FR5994 microcontroller for hardware validation. A series of statistical tests are then run against the simulation results to analyze overall randomness, including NIST and the Law of the Iterated Logarithm; the system passes both. The implementation on hardware is compared against a stream cipher variation and AES-128. The block cipher proposed outperforms AES-128 in terms of computation time and consumption for small block sizes. While not as secure, the cryptosystem is more scalable to block sizes used in IoT devices. / Master of Science / An Internet-of-Things (IoT) device is a single-purpose computer that operates with less computing resources and sometimes on battery power. The classification of IoT can range anywhere from motion sensors to a doorbell camera, but IoT devices are used in more than just home automation. The medical and industrial spaces use simple wireless computers for a number of tasks as well. One concern with IoT, given the hardware constraints, is the lack of security. Since messages are often transmitted through a wireless medium, anybody could eavesdrop on what is being communicated if data is not encrypted prior to transmission. Cryptography is the practice of taking any string of data and obfuscating it through a process that only valid parties can reverse. The sophistication of cryptographic systems has increased to the point where IoT manufacturers elect to use no security in many cases because the hardware is not advanced enough to run them efficiently. The Advanced Encryption Standard (AES) is usually the choice for security in the IoT space, but typically only higherend devices can afford to use AES. This thesis focuses on alternative lightweight systems to AES. First, a single-stage residue number system (RNS) pseudorandom number generator (PRNG) is analyzed, which has been proven to generate statistically random outputs in previous publications. PRNGs are a cheap method of producing seemingly random outputs through an algorithm once provided with an initial state known as a seed. An intelligent attack on the PRNG is devised, which is able to reverse engineer the initial state, effectively breaking the random behavior. Three defenses against the attack are then implemented to protect against the reported vulnerability. Following, a block cipher combination technique is presented, using the aforementioned PRNG as the source of randomness. A block cipher is a method of encrypting large chunks of data together, to better obfuscate the output. Using a block cipher is more secure than just using a PRNG for encryption. However, PRNGs are used to generate the key for the proposed block cipher, as they offer a more efficient method of security. The combination technique presented serves to increase the security of PRNGs further. The cipher is shown to perform better on an IoT-caliber device in terms of computation time and energy consumption at smaller block sizes than AES.

Master of Science / Department of Electrical and Computer Engineering / Balasubramaniam Natarajan / In recent years, orthogonal frequency division multiplexing (OFDM) scheme has received significant research interest due to its capability of supporting high data rates in hostile environments. As compared to conventional single-carrier modulation schemes, OFDM benefits from low complexity equalization filters and high spectral efficiency. A multiple access implementation of OFDM, i.e., orthogonal frequency division multiple access (OFDMA) has been considered as the multiple access (MA) scheme in 3GPP LTE, or LTE advanced downlink. In cellular OFDMA, frequency hopping (FH) is widely used to exploit frequency diversity gain and improve system throughput; and pilot patterns that have low-cross correlation are employed to improve the quality of channel estimation. However, there are numerous unsolved problems that need to be addressed in frequency hopped and pilot assisted OFDMA systems. Surveying the prior works in the literature, we find that limited research efforts have focused on coping with the inherent disadvantages regarding OFDM in cellular OFDMA systems. In this thesis, we employ the so-called residue number system (RNS) arithmetic concentrating on (a) FH pattern design for minimizing/averaging intra/inter-cell interference, (b) pilot pattern design for improving the quality of channel estimation, and (c) pilot pattern design for facilitating time-frequency synchronization and device identification in multi-cell OFDMA. Regarding (a), RNS-based FH patterns not only preserve orthogonality within the same cell, but also have the minimum number of symbol collisions among adjacent cells. Additionally, the RNS-based method exhibits consistent system performance and more frequency diversity gains as compared to previous efforts. With respect to (b), RNS-based pilot pattern design generates more unique pilot patterns than conventional methods. This results in low probability of pilot-to-pilot collisions, which in turn, significantly improves the quality of channel estimation from the system level perspective. For (c), as a special case of linear congruence sequences, RNS-based pilot patterns have good auto-correlation properties, which are extremely helpful in time-frequency synchronization and device identification.

Στα σύγχρονα ψηφιακά συστήματα η ανάγκη για γρήγορους υπολογισμούς είναι πλέον από τους πιο καθοριστικούς παράγοντες. Άλλοι ιδιαίτερα κρίσιμοι παράγοντες είναι η απαιτούμενη επιφάνεια του κυκλώματος και η κατανάλωση ενέργειας. Ωστόσο, ο χρόνος παραμένει ένας από τους πιο σημαντικούς για πλήθος εφαρμογές. Τα αριθμητικά κυκλώματα, όπως αθροιστές, πολλαπλασιαστές και κυκλώματα ύψωσης στο τετράγωνο, είναι πλέον αναπόσπαστο κομμάτι των ψηφιακών κυκλωμάτων, γι’ αυτό η επιτάχυνση των λειτουργιών αυτών είναι ένας στόχος στην κατεύθυνση του οποίου πολλές διαφορετικές αρχιτεκτονικές έχουν προταθεί. Η μείωση της καθυστέρησης στις αριθμητικές μονάδες θα δώσει μεγάλη βελτίωση στη συνολική απόδοση των συστημάτων, μιας και οι περισσότερες εφαρμογές εμπεριέχουν πλήθος αριθμητικών πράξεων. Η πράξη της ύψωσης στο τετράγωνο αποτελεί ειδική περίπτωση της πράξης του πολλαπλασιασμού, στην οποία ο πολλαπλασιαστέος ισούται με τον πολλαπλασιαστή. Ο λόγος για τον οποίο χρησιμοποιούμε εξειδικευμένα κυκλώματα για την πράξη αυτή είναι η εκμετάλλευση του γεγονότος ότι τα δύο έντελα είναι ίσα, κάτι που οδηγεί σε ελαχιστοποίηση του χρόνου που απαιτείται για την ολοκλήρωση της πράξης, αλλά και μείωση της απαιτούμενης επιφάνειας. Η πράξη της ύψωσης στο τετράγωνο χρησιμοποιείται σε πολλές εφαρμογές των υψηλής απόδοσης επεξεργαστών ψηφιακού σήματος (digital signal processors – DSP). Τέτοιες εφαρμογές συμπεριλαμβάνουν φιλτράρισμα σήματος (signal filtering), επεξεργασία εικόνας (image processing), και διαμόρφωση για τηλεπικοινωνιακά συστήματα. Η πράξη της ύψωσης στο τετράγωνο μπορεί, επίσης, να χρησιμοποιηθεί αποδοτικά στην υλοποίηση κρυπτογραφικών αλγορίθμων για την αποφυγή της χρονοβόρας διαδικασίας της ύψωσης σε δύναμη. Το Σύστημα Αριθμητικής Υπολοίπων (RNS), είναι ένα αριθμητικό σύστημα το οποίο παρουσιάζει σημαντικά πλεονεκτήματα στην ταχύτητα με την οποία μπορούν να γίνουν οι αριθμητικές πράξεις. Στο RNS οι αριθμοί αναπαρίστανται σαν ένα σύνολο από υπόλοιπα. Για να αναπαραστήσουμε έναν αριθμό ορίζουμε ένα σύνολο από πρώτους μεταξύ τους ακεραίους που ονομάζεται βάση του συστήματος P={p1,p2,…pk}. Η αναπαράσταση ενός αριθμού X στο RNS ορίζεται ως το σύνολο των υπολοίπων του Χ ως προς τα στοιχεία της βάσης Ρ. Προκύπτει, έτσι, ότι X={x1,x2,…,xk} όπου το xi είναι το υπόλοιπο της διαίρεσης του X με το στοιχείο της βάσης pi και συμβολίζεται με Xi=|X|pi. Κάθε ακέραιος Χ που ανήκει στο εύρος τιμών 0<=X<M, όπου Μ είναι το γινόμενο όλων των στοιχείων της βάσης P, έχει μοναδική αναπαράσταση στο RNS. Μια αριθμητική πράξη δύο εντέλων, η οποία μπορεί να είναι πρόσθεση, αφαίρεση ή πολλαπλασιασμός, ορίζεται ως εξής: {z1,z2,…,zk} = {x1,x2,…,xk}*{y1,y2,…,yk}, όπου zi = (xi*yi) modpi. Συνεπώς, κάθε αριθμητική πράξη εφαρμόζεται σε παράλληλες μονάδες (μία για κάθε στοιχείο της βάσης), καθεμία από τις οποίες διαχειρίζεται μικρούς αριθμούς (υπόλοιπα), αντί μιας μονάδας που θα χρειαζόταν να διαχειριστεί μεγάλους αριθμούς. Ένα από τα πιο δημοφιλή σύνολα βάσης είναι αυτά της μορφής {2^n, 2^n -1, 2^n+1}, λόγω του ότι προσφέρουν πολύ αποδοτικά κυκλώματα με κριτήριο το γινόμενο της επιφάνειας επί το τετράγωνο της καθυστέρησης (area * time^2), καθώς επίσης και αποδοτικούς μετατροπείς από και προς το δυαδικό σύστημα. Για το λόγο αυτό η υλοποίηση αποδοτικών modulo(2^n-1) και modulo(2n+1) κυκλωμάτων είναι σημαντική. Το πρόβλημα που παρουσιάζεται είναι ότι ενώ οι modulo(2^n) και modulo(2^n-1) αριθμητικές χρειάζονται το πολύ n δυαδικά ψηφία για την αναπαράσταση όλων των δυνατών υπολοίπων, στη modulo(2^n+1) αρχιτεκτονική χρειάζονται (n+1) ψηφία. Το πρόβλημα αυτό λύνεται με τη χρήση diminished-1 αναπαράστασης. Στη diminished-1 αναπαράσταση, κάθε αριθμός Χ αναπαρίσταται ως X-1=X-1. Έτσι, απαιτούνται n δυαδικά ψηφία για την αναπαράσταση, χρειάζονται, όμως, κυκλώματα μετατροπής από και προς την diminished-1 αναπαράσταση. Όταν χρησιμοποιείται η diminished-1 αναπαράσταση η τιμή εισόδου ίση με 0 χειρίζεται ξεχωριστά. Στα πλαίσια της εργασίας αναλύονται υπάρχουσες αρχιτεκτονικές και προτείνονται νέες για κυκλώματα ύψωσης στο τετράγωνο στο Σύστημα Αριθμητικής Υπολοίπων (RNS). Οι προτεινόμενες αρχιτεκτονικές βελτιώνουν την καθυστέρηση και, ταυτόχρονα, μειώνουν τις απαιτήσεις σε επιφάνεια. / Fast computations are of major importance in modern digital systems. Other critical factors are the area and the energy consumption. However, delay is still one of the most important ones for a variety of applications. Due to the fact that arithmetic circuits, such as adders, multipliers and squarers, have been integral components of most digital systems, many schemes have been proposed in the direction of accelerating arithmetic operations. As most applications contain a big number of arithmetic operations, delay reduction in arithmetic units will lead to significant improvement in the total system’s performance. Squaring is a special case of multiplication, where the multiplier equals the multiplicand. The reason for using a special circuit for squaring is to benefit from the fact that the two operands are equal, which reduces the delay and the area needed for the calculation of the square. The squaring operation is used in many applications of high performance digital signal processors. Such applications include signal filtering, image processing and modulation of communication components. Squarers can also find applicability in several cryptographic algorithms for the implementation of modular exponentiations. The Residue Number System is an arithmetic system in which arithmetic operations can be calculated in high speed. In the RNS numbers are represented as a set of residues. In order to represent a number we define a set of pairwise relative prime integers P={p1,p2,…pk}, which is the system’s base. Every number X is represented with the set of the residues occurred after the division of X by each element of the base, P. Thus, X={x1,x2,…,xk}, where xi stands for the residue of the division of X by the ith element of the base, pi, which is denoted as Xi=|X|pi. In the RNS there is a unique representation for every integer X that 0<=X<M, where M is the product of all the elements of the base. A two-operant arithmetic operation, which can be an addition, a subtraction or a multiplication, is defined as {z1,z2,…,zk} = {x1,x2,…,xk}*{y1,y2,…,yk}, where zi = (xi*yi) modpi. Consequently, arithmetic operations are performed to parallel units (one unit for each element of the base) each one handling small residues, instead of a single unit that handles large numbers. One of the most popular base sets is those of the form {2^n, 2^n -1, 2^n+1}, due to the fact that they offer very efficient circuits when considering the area*time^2 criterion and efficient converters from/to the binary system. Thus, the design of efficient modulo (2^n-1) and modulo (2^n+1) circuits is of high importance. The problem that arises is that while in modulo(2^n) and modulo(2^n-1) arithmetic n bits are sufficient for the representation of all possible residues, in modulo(2^n+1) arithmetic (n+1) bits are needed. This can be solved by the use of the diminished-1 representation. In the diminished-1 representation every number X is represented as X-1=X-1. Therefore, n bits are sufficient for the representation, but converters from/to the diminished-1 representation are needed. In cases that the diminished-1 representation is used, operands with value 0 is treated separately. For the needs of this thesis, existing architectures of squaring circuits in the RNS are studied and new ones are proposed. The proposed architectures improve the system’s delay, while, in parallel, reduce the area needs.