The <rsa.h> header file
This header file contains the following functions:
BN_power17Mod BN_powerMod BN_prodMod cdecrypt
MD5Done MD5Init MD5Final MD5Update
and the following predefined types:
BN MD5_CTX
Functions
void BN_prodMod (BN *dest, const BN *b, const BN *n);
Multiplies two big integers modulo n.
BN_prodMod calculates Y = (Y * B) mod N
where Y, B and N are big integers (up to 2040 bits) stored in
BN structures pointed to by dest, b and n respectively.
This routine is used in TIOS for RSA encryption, but may be used for any other purposes too
(see BN for more info about how RSA works).
Here is an example of program which takes three (eventually big) integers A, B and N, calculates
(A * B) mod N and returns the result (assuming that A, B
and N are really integers, i.e. no checking is implemented). This program also ilustrates how you
can get "big" integers from the expressions stack, and push them to it:
#define RETURN_VALUE
#include <alloc.h>
#include <estack.h>
#include <rsa.h>
int _ti89, _ti92plus;
#define GetBignumArg(ap, bn) \
({unsigned char __n = *--(unsigned char*)(ap); \
char *__p = (char*)(bn) + __n; \
(bn)->Len = __n; \
while (__n--) *__p-- = *--(ap); \
(void)*(ap)--; })
void push_Bignum (BN *bn)
{
unsigned m, n = bn->Len;
char *p = (char*)bn;
m = n;
while (n--) push_quantum (*++p);
push_quantum_pair (m, POSINT_TAG);
}
void _main (void)
{
ESI argptr = top_estack;
BN *a = malloc (256), *b = malloc (256), *c = malloc (256);
GetBignumArg (argptr, a);
GetBignumArg (argptr, b);
GetBignumArg (argptr, c);
BN_prodMod (a, b, c);
push_Bignum (a);
free (a); free (b); free (c);
}
void BN_powerMod (BN *dest, const BN *x, const BN *e, const BN *n);
Raises a big integer to the e-th power modulo n.
BN_powerMod calculates Y = (X ^ E) mod N
where Y, X, E and N are big integers (up to 2040 bits) stored in
BN structures pointed to by dest, x, e and n respectively.
This routine is used in TIOS for RSA encryption, but may be used for any other purposes too
(see BN for more info about how RSA works).
void BN_power17Mod (BN *dest, const BN *x, const BN *n);
Raises a big integer to the 17-th power modulo n.
BN_power17Mod calculates Y = (X ^ 17) mod N
where Y, X and N are big integers (up to 2040 bits) stored in
BN structures pointed to by dest, x and n respectively.
This is main routine for RSA decryption used in cdecrypt
(see BN for more info about how RSA works).
void cdecrypt (BN *dest, char *src, unsigned long size, BN *public_key);
Decrypt a message.
cdecrypt decrypts the message pointed to by src which is size butes long using
the public key pointed to by public_key, and stores decrypted message in
BN structure pointed to by dest (see BN for more info
about how RSA works). Note that the message must be short enough to be decrypted in
the structure pointed to by dest, because BN structure is maximally
255 bytes long.
TIOS use decryption with public key (N,17) where N is a 512-bit (64-byte) key,
given at the beginning of the certificate code, although others may (or may not) be used.
That's why it uses BN_power17Mod. Generally, for usage in RSA,
N must be equal to P * Q, where P and Q are large primes, and
where (P-1) * (Q-1) is relatively prime to 17 (other part of the key).
void MD5Init (MD5_CTX *context);
Initializes Message-Diggest context for usage in MD5 algorithm.
MD5Init begins a MD5 Message-Diggest Algorithm, i.e. fills the MD5_CTX
structure pointed to by context with necessary data. MD5 is the algorithm which takes
as input a message of arbitrary length and produces as output a 128-bit "fingerprint" or
"message digest" of the input. It is conjectured that it is computationally infeasible to
produce two messages having the same message digest, or to produce any message having a
given prespecified target message digest. The MD5 algorithm is intended for digital signature
applications, where a large file must be "compressed" in a secure manner before being
encrypted with a private (secret) key under a public-key cryptosystem such as RSA
(see BN for more info about how RSA works).
void MD5Update (MD5_CTX *context, unsigned char *input, unsigned short InputLen);
Process a message block using MD5 algorithm.
MD5Update performs a MD5 block update operation. It continues an MD5 message-digest operation,
by processing InputLen-byte length message block pointed to by input, and
by updating the MD5 context pointed to by context. MD5Update may be called as many times
as necessary, so the message may be processed in blocks. See also MD5Init.
void MD5Final (unsigned char digest[16], MD5_CTX *context);
Ends an MD5 operation and produces a Message-Digest.
MD5Final finalizes MD algorithm, i.e. ends an MD5 Message-Digest operation, writing the
Message-Digest in the buffer pointed to by digest in according to the information
stored in context. See also MD5Init.
void MD5Done (BN *digest, MD5_CTX *context);
Produces a Message-Digest as a big integer.
MD5Done is very similar as MD5Final. It calls MD5Final,
but stores the computed Message-Digest in BN structure pointed to by
digest (i.e. stores the length byte in digest[0]). This function is the
only extension to MD5 package invented by TI: all other functions is picked up from the
original MD5 package, but optimized for 16-bit processors (instead of 32-bit).
Predefined types
BN is a structure type for describing very large integers (up to 2040 bits). It is defined as
typedef struct
{
unsigned char Len;
unsigned char Data[0]; // Variable length - should be []
} BN;
Note that Data contains the number in little endian format.
TIOS uses big integers for implementing RSA criptography algorithm to authenticate
(digitally sign) ROM images (and flash applications), more precise, to protect actual
ROM/Flash certificate data (see cert.h header file).
The basic ideas of RSA are as follows: under certain conditions, function
Y = (X ^ A) mod N
has function
X = (Y ^ B) mod N
as its inverse function, where parameter B depends, of course, of A and N.
But, computing B from A and N requires that the prime factors of N are known.
Now, suppose that N = P * Q, where P and Q are large primes,
such that nobody can factor N in a real time. Suppose also that somebody
(person XXX for example) knows two large primes P and Q. Person XXX can compute
N = P * Q. After this, he may insist (for security reasons) that
anybody which wants to send the message to XXX must to encode the message using
the formula Y = (X^A) mod N,
where X is an original message, and Y is encoded message. Constants A and N
may be published without any danger, and pair (N,A) is so-called public key.
XXX may decrypt encoded message Y using the formula
X = (Y^B) mod N
because XXX can calculate B (he knows the prime factor of N). But
note that nobody else can decrypt X, because nobody else knows prime factors of N a priori,
and they can not be computed in a real time. Pair (N,B) is so-called private key.
This is only a half of the story. Suppose that person XXX wants to send a
message to person YYY. He will encrypt the message with the public key of
person YYY. YYY will, of course, decrypt the message with his private key.
But, suppose that XXX send together with encoded message another message
(called "signature") which is encoded using formula
Y = (X^B) mod N, i.e.
using PRIVATE key of XXX. Then, if YYY tries to decode such message using
PUBLIC key of XXX, he must get original message too (so, he will receive
two identical copies of the message). But, after this, YYY can be sure
that really XXX sent the message (not some third person), because nobody else
can compute B from A, i.e. nobody else can produce a message which can be
decrypted using the public key of XXX!
To summarize: the RSA algorithm uses two keys, one is public and one private.
Data encrypted with one of these keys can only be decrypted with the other key.
So given the procedure is secure, data encryped with the public key can only be
decrypted with the private key, and valid data decrypted with the public key
could only be produced by the private key.
MD5_CTX is a structure type for describing the context data used for implementing MD5
Message-Digest Algorithm. It is defined as
typedef struct
{
unsigned long state[4]; // state (ABCD)
unsigned long count[2]; // number of bits modulo 2^64 (lsb first)
unsigned char buffer[64]; // input buffer
} MD5_CTX;
MD5 is the algorithm which takes as input a message of arbitrary length and produces as output
a 128-bit "fingerprint" or "message digest" of the input. It is conjectured that it is
computationally infeasible to
produce two messages having the same message digest, or to produce any message having a
given prespecified target message digest. The MD5 algorithm is intended for digital signature
applications, where a large file must be "compressed" in a secure manner before being
encrypted with a private (secret) key under a public-key cryptosystem such as RSA
(see BN for more info about how RSA works). Summary, message digests create
a unique number for given data. By sending a message digest encrypted with the private key,
along with the original message, it is possible to check that the message came from the correct
source. This is done by generating the message digest, and comparing it against the encrypted
version sent along with the message (decrypted with the public key). If they match, then this
"authenticates" the message.
TI implements the MD5 Message-Digest Algorithm optimised for 16 bit operation rather
than 32 bit operation as in original algorithm. The code is based on "RSA Data Security,
Inc. MD5 Message-Digest Algorithm". A good reference and source code for this algorithm
can be found at [RFC1321].