Wednesday, May 13, 2009

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.

Saturday, May 9, 2009

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

Friday, May 8, 2009

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);
}
}