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

Sci-Tech Friendly President

Today, Obama announced the launch of a new agency, ARPA-E which stands for Advanced Research Projects Agency - Energy. The agency is modeled after DARPA (Defense - ARPA). The science-and-technology friendly US president is also planning to increase the allocated budget for science and technology to 3% of GDP, which is translated to about $240 billion.

Obama also said that he wants to make solar cells as cheap as paints, self-power buildings (smart building?) and some other interesting sci-tech researches. We will see breakthroughs in coming years produced by US national labs again, after deteriorated by wrong policies of Bush who is not-science-but-war friendly ex president.

Shall we start buying technology stocks once again? I am thinking that energy-related technologies will be booming, smart building system which can conserver more energy, which includes home automation that can control energy consumption to be more efficient, faster routers (we live in a connected world, don't we?), robotics will be more advanced, etc. Many new hi-tech jobs will be available.

I think 99% scientists and engineers should love this president.

Bravo to Obama!