Mathematical Advances Strengthen IT Security

European Science Foundation (05/11/09) Valleley, Sofia

A new cryptography approach based on the mathematical theory of elliptic curves is considered a leading candidate to replace the widely used RSA public key security system. Elliptic curves could enable more efficient cryptography and provide an optimum combination of security and processing efficiency.

The European Science Foundation (ESF) recently held a workshop to discuss the potential for elliptic curves and other modern techniques of mathematics in cryptography and information technology security.

"The impact of the elliptic curve method for integer factorization has played a role in introducing elliptic curves to cryptographers, albeit for attacking the underlying problem on which RSA is based (the difficulty of factoring integers)," says David Kohel, convenor of the ESF workshop, from the Institut de Mathematiques de Luminy in Marseille, France. Kohel says the advantage of elliptic curve cryptography is its immunity to the specialized attacks that have degraded the strength of RSA, meaning smaller keys can be used to provide the same levels of protection.

"In general, the cryptographer has the benefit over the cryptanalyst (the person attacking the cryptosystem) as he or she can select the key size for any desired level of security, provided everyone has the same base of knowledge of best attacks on the underlying cryptosystem," he says.

Various Embedded Systems

Sony Clie NX80V PDA (running Palm OS)
The NX80V runs Palm OS 5.0 and has a 200 MHz XScale processor. It has 32 megs of RAM, 15.5 of which is available to the user.

AT&T HTC 8125 SmartPhone

Processor:	200 MHz TI OMAP850
Operating System:	Windows Mobile 5.0
Memory:	64 MB RAM; 128 MB flash ROM (43 MB available)

In European version is Qtek 9100, AKA The HTC Wizard.
Linux port: http://linwizard.wiki.sourceforge.net/

Computer Architecture: A Quantitative Approach

Powered by Ingram Digital

Branch Prediction Algorithm

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

/******************************************************************************
Branch Prediction Simulator
(c) M. Lutfi, 2009
 ******************************************************************************/
#define ROW_MAJOR_ADDR(A, r, c, n)  ((A) + (r)*(n) + (c))
typedef enum {
    not_taken = 0,
    taken
} branch_t;

typedef enum {
    strongly_not_taken  = 0,
    weakly_not_taken,
    weakly_taken,
    strongly_taken
} branch_state_t;

typedef struct {
    unsigned int    correctPredictionCount;
    branch_state_t  state;
    unsigned int    n_iter;
} lbp_t;

enum {
    BRANCH_A = 0,
    BRANCH_B,
    BRANCH_C,
    BRANCH_D,
    N_OF_BRANCHES
};

#define NBITS_OF_GBH    3    // number of bits in Global History register

lbp_t lbp_table[NBITS_OF_GBH][N_OF_BRANCHES];


unsigned char    gbh=0;  // global branch history register (3-bit only)
branch_t    last_outcome = not_taken;


char* get_branch_state_str(branch_t b)
{
    if (b == not_taken)
    return "not_taken";
    else
    return "taken";
}

void update_gbh(void)
{
#if 0
    gbh = (gbh<<1) | last_outcome;
    gbh &= ((1<    printf("last_outcome = %s\n", get_branch_state_str(last_outcome));
    printf("gbh = %0X\n", gbh);
#endif
}

/* Local Branch Prediction FSM */
void lbp_update(lbp_t *lbp, branch_t outcome)
{
   switch (lbp->state) {
    case strongly_not_taken:
        if (outcome == taken) {
        lbp->state = weakly_not_taken;
        } else {
        lbp->correctPredictionCount++;
        }
        break;
    case weakly_not_taken:
        if (outcome == taken) {
        lbp->state = weakly_taken;
        } else {
        lbp->state = strongly_not_taken;
        }
        break;
    case weakly_taken:
        if (outcome == taken) {
        lbp->state = strongly_taken;
        } else
        lbp->state = weakly_not_taken;
        break;
    case strongly_taken:
        if (outcome == taken) {
        lbp->correctPredictionCount++;
        } else {
        // the outcome is NT
        lbp->state = weakly_taken;
        }
        break;
    }
    lbp->n_iter++;
}


int fun(double *p, int n)
{
    int r = 0;
    int c = 0;
    double *pA;

    while (r <= n-1) {
    last_outcome = not_taken;
    update_gbh();
    lbp_update(&lbp_table[gbh][BRANCH_A], not_taken);
    while (c <= n-1) {
        last_outcome = not_taken;
        update_gbh();
        pA = ROW_MAJOR_ADDR(p, r, c, n);
        if (r < c) {
        lbp_update(&lbp_table[gbh][BRANCH_C], not_taken);
            *pA = 2* (*pA) + 1;
        last_outcome = not_taken;
        } else {
        lbp_update(&lbp_table[gbh][BRANCH_C], taken); 
        last_outcome = taken;
        }

        if (r > c) {
        lbp_update(&lbp_table[gbh][BRANCH_D], not_taken);
        *pA = 2* (*pA) - 1;
        last_outcome = not_taken;
        } else {
        lbp_update(&lbp_table[gbh][BRANCH_D], taken);
        last_outcome = taken;
        }
        ++c;
    }
    lbp_update(&lbp_table[gbh][BRANCH_B], taken);
    last_outcome = taken;
    update_gbh();
    ++r;
    }
    lbp_update(&lbp_table[gbh][BRANCH_A], taken);
    last_outcome = taken;
    update_gbh();
    return 0;
}

void print_A(double *p, int n)
{
    int i,j;
    double *pA;
   
    for (i=0; i<n; i++) {
    for(j=0; j<n; j++) {
        pA = ROW_MAJOR_ADDR(p, i, j, n);
        if (!pA) return;
        printf("%d: &A[%d][%d] = %0X,\t", __LINE__, i, j, pA);
        printf("%d: A[%d][%d] = %lf\n", __LINE__, i, j, *pA);
    }
    }
}

void init_gbh(void)
{
    int i,j;
    lbp_t *lbpP;
   
    gbh = 0;
    for(i=0; i<(NBITS_OF_GBH<<3); i++) {
    lbpP = (lbp_t*)&lbp_table[i];
    for(j=0; j<N_OF_BRANCHES; j++) {
        lbpP[j].correctPredictionCount = 0;
        lbpP[j].state = weakly_not_taken;
        lbpP[j].n_iter = 0;
    }
    }
}

int main(void)
{
    #define N 50
    double A[N][N];
    int i,j;

    init_gbh();  
    printf("sizeof(double) = %d\n", sizeof(double));
    printf("%d: &A = %0X\n", __LINE__, &A[0][0]);
    for(i=0; i<N; i++) {
    for(j=0; j<N; j++) {
        A[i][j] = ROW_MAJOR_ADDR(1, i, j, N);
    }
    }
    fun(&A[0][0], N);
    printf("gbh = %0X\n", gbh);
    for(i=0; i<N_OF_BRANCHES; i++) {
    printf("lbp[%d] iteration = %d\n", i, lbp_table[gbh][i].n_iter);
    printf("lbp[%d] correct prediction count = %d\n",
        i, lbp_table[gbh][i].correctPredictionCount);
    printf("Correct Prediction Rate = %4.2lf%\n\n",
      ((double)(lbp_table[gbh][i].correctPredictionCount)/(double)lbp_table[gbh][i].n_iter) *100.0);
    }
}

ARM EABI Environment

To develop Linux system with TI 35xx as a target, we need to have the toolchains, build-essential root filesystem and Linux kernel.

Here are the links for some useful packages:

http://armel.applieddata.net/developers/linux/eabi/armel-root-fs.tar.bz2
http://armel.applieddata.net/developers/linux/eabi/armel-root-fs.tar.bz2.md5


http://wiki.debian.org/ArmEabiPort
CodeSourcery GNU: http://www.codesourcery.com/sgpp/lite/arm/portal/release642