"Andreas Plesner Jacobsen" <apj@daarligstil.dk> skrev i en meddelelse
news:slrna0mgko.s5i.apj@slartibartfast.nerd.dk...
> In article <3c0b29dc$0$263$edfadb0f@dspool01.news.tele.dk>, Lene wrote:
Som jeg skrev i mit første indlæg, så er jeg ikke instillet på en større
debat om hvor randum de pågældende data er. Det er rigtigt at en ægte OTP
kryptering kræver 100% random data, og de data TSC genererer er ikke det,
dertil har du rat, men de er med de analyser jeg har lavet ganske tæt på. En
anden vigtig ting er jo at de kun anvendes en og kun en gang.
Men det er næsten umuligt at debaterer her, når du ikke har sat dig grundigt
ind i programmets virkemåde, alle de svar du vil have står i vejledningen.
> Og hvordan er det lige man genererer tilfældige tal på en computer?
> Bitlængden er fuldstændig irrelevant, da hele konceptet er fejlbehæftet.
> Som jeg læser teksten udvander de faktisk tilfældighedskonceptet
> yderligere end blot at påstå at de laver OTP strømme ud fra
> pseudotilfældighedsgeneratorer.
Her lidt om random data og deres anvendelse:
The Random Bits Bin - A True Source of Random Bits
The Random Bits Bin is a file called RandomBitsBin.rbb that is created and
maintained by Top Secret Crypto. It is 8,192 bytes, or 65,536 bits, long,
and once it is read into memory, it is constantly being changed by Top
Secret Crypto. Any time a seed, key, or numeric value, such as Prime p or q,
is required by Top Secret Crypto, it is extracted from somewhere within the
Random Bits Bin. When you exit the program, the RandomBitsBin.rbb file is
updated with the current contents of the Random Bits Bin in memory, thus
creating a new RandomBitsBin.rbb file for the next time you use Top Secret
Crypto.
The big question everyone is asking themselves right now is, how can a
computer be a source of random bits?
Every computer has a system timer. In the case of most Intel® and Intel®
compatible computers, it beats with a frequency of 1.193 million times per
second. This system timer, or high resolution performance timer, can be read
by any computer program. There is also a Read Timestamp Counter Instruction,
rdtsc, that increments with each clock cycle of your computer. This
instruction is available on most Intel® Pentium and AMD Pentium compatible
computers. If you have a 400 MHz processor, the Timestamp Counter will
increment 400,000,000 times per second. Because of the high frequency of the
Timestamp Counter in today's computers, it is the preferable instruction to
use.
Top Secret Crypto sets up, and runs, a separate thread whose sole function
is to read the system timer, or Timestamp Counter, and update the Random
Bits Bin. Since the thread does not have control all the time, there is no
way of predicting the value in the system timer or Timestamp Counter when
the thread does get control. This is because Windows® is a multitasking
operating system running many programs and threads and constantly shifting
between them. The first time the system timer or Timestamp Counter is read,
its low 8 bits are XNORed with the first 8 bits of the Random Bits Bin. The
next time it is read, the next 8 bits are XNORed with the low 8 bits of the
system timer or Timestamp Counter. When you reach the end of the Random Bits
Bin, you start over at the beginning. You can readily see that there is no
underlying system to the generation of the random data.
Due to the speed of the computer, the entire contents of the Random Bits Bin
may change many thousands of times per second. To prove my point, fire up
Top Secret Crypto and let it run for only a second or two. Take a look at
the contents of the RandomBitsBin.rbb file and you will see how random the
data in it is.
For all you computer jockeys out there who do not know what XNOR means, I
will now tell you. It is an xor operation followed by a not operation.
Note: The Read Timestamp Counter Instruction is used by registered programs,
while the system timer is used by non-registered programs.
Random Bits Bin Source Code
Before delving into the source code please read about the Random Bits Bin
and extracting random bits from the Random Bits Bin.
Random Bits Bin Setup Source Code
// Make sure we have a High Performance Counter in the system
// to generate random bits for the Random Bits Bin.
//...........................................................
if (!QueryPerformanceFrequency(&PerformanceCounter))
{
MessageBoxProc(hWnd,IDS_INITIALIZE,IDS_NOHPC,MB_USERICON | MB_OK,
MB_ICONHAND,lpszStopSign);
return(FALSE);
}
// Allocate the memory for the random bits bin.
//.............................................
pRandBitsBin = AllocateMemory(RBB_LENGTH);
if (pRandBitsBin)
{
// Initialize the memory to A5 hex
//................................
int i;
pMem = pRandBitsBin;
for (i = 0; i < RBB_LENGTH; i++)
*pMem++ = LOBYTE(LOWORD(FillChar));
}
else
{
MessageBoxProc(hWnd,IDS_INITIALIZE,IDS_NOMEM,MB_USERICON | MB_OK,
MB_ICONHAND,lpszStopSign);
return(FALSE);
}
// Create or open the Random Bits Bin file.
// ........................................
hFile = CreateMyFile((LPTSTR)&RandomBitsFile,GENERIC_READ |
GENERIC_WRITE,0,NULL,
OPEN_ALWAYS,FILE_ATTRIBUTE_NORMAL,NULL);
if (!hFile)
{
MessageBoxProc(hWnd,IDS_INITIALIZE,IDS_NOCREATE,
MB_USERICON | MB_OK,
MB_ICONHAND,lpszStopSign);
return(FALSE);
}
// Determine if we opened or created the file. If we opened it,
// read the file into the random bits bin buffer. If we created
// it, write the initial buffer to disk.
//.............................................................
if (GetLastError() == ERROR_ALREADY_EXISTS)
{
if (GetFileSize(hFile,NULL) != RBB_LENGTH)
{
if (MessageBoxProc(hWnd,IDS_INITIALIZE,IDS_WRONGLGTH,
MB_USERICON | MB_OKCANCEL | MB_DEFBUTTON1,
MB_ICONQUESTION,lpszQuestion) == IDCANCEL)
{
return(FALSE);
}
else
{
SetEndOfFile(hFile);
bResult = WriteMyFile((LPTSTR)&RandomBitsFile,hFile,
pRandBitsBin,RBB_LENGTH,
d_Write,NULL);
if (!bResult)
{
MessageBoxProc(hWnd,IDS_INITIALIZE,IDS_NOCREATE,
MB_USERICON | MB_OK,MB_ICONHAND,
lpszStopSign);
return(FALSE);
}
}
}
else
{
bResult = ReadMyFile((LPTSTR)&RandomBitsFile,hFile,
pRandBitsBin,
RBB_LENGTH,&dwRead_Write,NULL);
if (!bResult)
{
MessageBoxProc(hWnd,IDS_INITIALIZE,IDS_NOCREATE,
MB_USERICON | MB_OK,MB_ICONHAND,
lpszStopSign);
return(FALSE);
}
}
}
else
{
bResult = WriteMyFile((LPTSTR)&RandomBitsFile,hFile,
pRandBitsBin,RBB_LENGTH,
&dwRead_Write,NULL);
if (!bResult)
{
MessageBoxProc(hWnd,IDS_INITIALIZE,IDS_NOCREATE,
MB_USERICON | MB_ICONHAND,lpszStopSign);
return(FALSE);
}
}
bResult = CloseMyHandle((LPTSTR)&RandomBitsFile,hFile);
if (!bResult)
{
MessageBoxProc(hWnd,IDS_INITIALIZE,IDS_NOCREATE,
MB_USERICON | MB_OK,MB_ICONHAND,lpszStopSign);
return(FALSE);
}
bUpdateRandBitsBin = TRUE;
// Start the thread that will handle the random bits bin.
// First create an event so we can tell the thread when to quit.
//..............................................................
hRBBEvent = CreateEvent(NULL,TRUE,FALSE,TEXT("RBB_SHUTDOWN_EVENT"));
if (!hRBBEvent)
{
MessageBoxProc(hWnd,IDS_INITIALIZE,IDS_NOEVENT,MB_USERICON | MB_OK,
MB_ICONHAND,lpszStopSign);
return(FALSE);
}
hRBBThread = CreateThread(NULL,0,RandomBitsBinThread,hWnd,0,&dwRBBThreadId);
if (!hRBBThread)
{
MessageBoxProc(hWnd,IDS_INITIALIZE,IDS_NOTHREAD,MB_USERICON | MB_OK,
MB_ICONHAND,lpszStopSign);
return(FALSE);
}
Update the Random Bits Bin File
The random bits bin file is updated with the current contents of the random
bits bin in memory just before you exit the program.
// Update the Random Bits Bin File using the Random Bits Bin in memory.
// We do not do any error checking because it should hardly ever fail.
//....................................................................
LRESULT CALLBACK UpdateRandBitsBinFile()
{
HANDLE hFile;
DWORD dwWrite;
BOOL bResult;
BOOL bReturnResult = FALSE;
if (bUpdateRandBitsBin)
{
// Stir up the bits before we write the bits bin to a file.
//.........................................................
StirTheBits();
// Open the file. It will always exist at this point.
//...................................................
hFile = CreateMyFile((LPTSTR)&RandomBitsFile,GENERIC_READ | GENERIC_WRITE,
0,NULL,OPEN_ALWAYS,FILE_ATTRIBUTE_NORMAL,NULL);
if (hFile)
{
bResult = WriteMyFile((LPTSTR)&RandomBitsFile,hFile,
pRandBitsBin,RBB_LENGTH,&dwWrite,NULL);
if (bResult)
{
bResult = CloseMyHandle((LPTSTR)&RandomBitsFile,hFile);
if (bResult)
{
bReturnResult = TRUE;
}
}
}
}
return(bReturnResult);
}
Random Bits Bin Thread Procedure
The following thread is created at the start of the program and runs
continuously, changing the random bits bin in memory. The only time it is
suspended is during RSA Key Generation to shorten the time is takes to
generate a set of RSA Keys.
What the code does is read the High Performance Counter or the Timestamp
Counter, performs an xor operation with the low 8 bits of the performance
counter or Timestamp Counter against one byte in the random bits bin,
performs a not on the byte in the random bits bin, and increments the random
bits bin pointer to point to the next byte. When you reach the end of the
random bits bin, you start over at the beginning. Due to the high speed of
today's computers, the entire contents of the random bits bin can change
many hundreds or thousands of times per second. This is a very effective
generator of random bits that can be used to seed pseudo random number
generators, or create One Time Pad Key Files, which are used to seed 256
pseudo random number generators.
Note: For those of you who track CPU usage on your computer, this thread
will cause the CPU usage rate to be at or near 100%. This is because every
time another program or thread says they are in an idle state waiting for
some kind of imput, this thread will use their idle time to randomize and
update the Random Bits Bin. Because of this your CPU usage will always
reflect at or near 100% when running Top Secret Crypto. This in no way
affects how other programs will run.
// Random Bits Bin thread procedure. This thread constantly updates
// and randomizes the random bits bin. It is run as a thread until
// the program is terminated.
//.................................................................
DWORD WINAPI RandomBitsBinThread(HWND hWnd)
{
int iRBBIndex = 0;
int iPCLowPart = 0;
LPBYTE pRBBBuffer;
// Open the event we will check for to see if we are shutting down.
//.................................................................
HANDLE hRBBEvent = OpenEvent(SYNCHRONIZE,FALSE,
TEXT("RBB_SHUTDOWN_EVENT"));
pRBBBuffer = pRandBitsBin;
while(TRUE)
{
// Read the high performance counter or the time stamp counter.
//.............................................................
if (bUseTimeStampCounter)
{
__asm
{
rdtsc
mov PerformanceCounter.LowPart,eax
}
}
else
{
QueryPerformanceCounter(&PerformanceCounter);
}
iPCLowPart = PerformanceCounter.LowPart;
*pRBBBuffer ^= LOBYTE(LOWORD(iPCLowPart));
*pRBBBuffer++ = ~*pRBBBuffer;
iRBBIndex += 1;
if (iRBBIndex >= RBB_LENGTH)
{
pRBBBuffer = pRandBitsBin;
iRBBIndex = 0;
}
if (WaitForSingleObject(hRBBEvent,0) == WAIT_OBJECT_0)
break;
}
CloseHandle(hRBBEvent);
return(TRUE);
}
Stir the Bits in the Random Bits Bin
This procedure stirs up the entire contents of the random bits bin at the
same time. It reads the High Performance Counter or Timestamp Counter, and
performs a xor and not operation on the first byte of the random bits bin
with the low 8 bits of the counter. It then takes the first byte of the
random bits bin and performs a xor and not between the first and second
bytes of the random bits bin storing the result in the second byte. The
operation is then performed between the results of the second and third
bytes, storing the results in the third byte. This operation is continued
until the end of the random bits bin is reached.
// Stir the bits of the random bits bin.
//......................................
VOID StirTheBits()
{
// Read the high performance counter or the timestamp counter.
//............................................................
if (bUseTimeStampCounter)
{
__asm
{
rdtsc
mov PerformanceCounter.LowPart,eax
}
}
else
{
QueryPerformanceCounter(&PerformanceCounter);
}
__asm
{
mov edi,pRandBitsBin
mov edx,PerformanceCounter.LowPart
mov al,byte ptr [edi]
xor al,dl
not al
stosb
mov ecx,RBB_LENGTH
dec ecx
Rbl:
mov dl,al
mov al,byte ptr [edi]
xor al,dl
not al
stosb
loop Rbl
}
}
Extract Random Bits from the Random Bits Bin
For every 32 bits or less requested, the High Performance Counter or
Timestamp Counter is read, and the low 16 bits of the High Performance
Counter or Timestamp Counter is used as an index into the random bits bin.
(The random bits bin is 8,192 bytes or 65,536 bits long.) This is the
starting point at which you will start to extract bits. If the index is
13,972 and you need to extract 32 bits, you will start at the 13,972nd bit
in the random bits bin and extract 32 bits. If you are constructing a large
number that requires many thousands of bits, the High Performance Counter or
Timestamp Counter will be read again, and the next 32 bits will be extracted
using the low 16 bits as an index. After every 32 bits is extracted, the
entire content of the random bits bin is stirred up before the next 32 bits
are extracted.
// Get the number of requested random bits from the random bits bin
// and place them in the destination address.
//.................................................................
VOID GetRandomBits(DWORD BitsRequested, LPVOID Destination)
{
DWORD Mask32;
LPVOID BitsDestination;
BitsDestination = Destination;
while (BitsRequested != 0)
{
if (BitsRequested >= 32)
{
BitsRequested -= 32;
Mask32 = -1;
}
else
{
__asm
{
mov Mask32,0
mov eax,-1
mov cl,byte ptr BitsRequested
shld Mask32,eax,cl
mov BitsRequested,0
}
}
// Read the high performance counter or the time stamp counter.
//.............................................................
if (bUseTimeStampCounter)
{
__asm
{
rdtsc
mov PerformanceCounter.LowPart,eax
}
}
else
{
QueryPerformanceCounter(&PerformanceCounter);
}
// Get up to 32 random bits and place them in the destination.
//............................................................
__asm
{
mov esi,pRandBitsBin
mov edi,BitsDestination
mov ebx,PerformanceCounter.LowPart
and ebx,0ffffh
mov ecx,ebx
shr ebx,5
shl ebx,2
dec ebx
and cl,1fh
mov eax,dword ptr [esi][ebx]
cmp ebx,8187
jne L1
mov edx,dword ptr [esi]
jmp L2
L1: mov edx,dword ptr [esi][ebx+4]
L2: shrd eax,edx,cl
and eax,Mask32
stosd
mov BitsDestination,edi
}
// We only stir the bits if we are using the High Performance counter.
//....................................................................
if (!bUseTimeStampCounter)
{
StirTheBits();
}
}
}
Note: The Read Timestamp Counter Instruction, rdtsc, is only used if your
computer supports the instruction, and you have registered Top Secret
Crypto. Most Intel® Pentium processors and AMD Pentium compatible processors
support this instruction.
Source Code and Algorithms: for the core procedures used by Top Secret
Crypto.
> Nej, RSA specificerer ikke hvordan nøgler genereres; for at gøre dette
> skal du generere disse meget store primtal. Da det er enormt
> beregningsintensivt at bevise at et tal er et primtal benytter man ofte
> nogle tests til at antyde at det er et primtal. Hvis disse tests ikke er
> gode nok vil man ofte ende med en RSA nøgle der er baseret på et eller
> to ikke-primtal.
Her har du svar på det:
Under The Hood: The Math Behind Public and Secret Keys
Top Secret Crypto extracts random bits from the random bits bin to seed
Primes p and q with starting values. A fast sieve method is used to weed out
most of the numbers that are not prime. Those that pass the fast sieve are
tested with Fermat's Theorem to see if it is a possible prime number. I say
possible, because some non prime numbers can pass the Fermat Test. These are
weeded out when the RSA Keys are tested. A prime candidate must pass 4
Fermat Tests to be considered almost 100% prime.
The Fermat Test applies Fermat's Theorem to prime candidate p: For any small
x, if (x(p-1)) Mod p is not equal to 1, then p is not prime. (Remember: Mod
means remainder.)
Once Primes p and q are found, the program calculates the rest of the
numbers needed in forming your Public and Secret Keys.
Phi(n) = (p-1)*(q-1)
G(n) = gcd(p-1, q-1) (gcd: greatest common divisor)
F(n)= Phi(n)/G(n) F(n) = lcm or least common multiple of p-1 and q-1.
Next Exponent e is calculated. This is used in your Public Key to encrypt
with. We always start with a small fixed odd value for e of 17. We look for
an e such that gcd (e, Phi(n)) = 1. If 17 does not work, we then add two to
e and try again. Most of the time 17 does work, and that is why Exponent e
for almost all public keys is 17, or 11 hexadecimal. This small value for
Exponent e makes for very fast encryption no matter what size Modulus n is.
Next Exponent d is calculated. This is used in your Secret Key to decrypt
with. Exponent d is the multiplicative inverse of e Mod F(n). We compute
Exponent d such that (e*d) Mod F(n) = 1.
Next Inverse u is calculated. This value is also used in your Secret Key.
Inverse u is the multiplicative inverse of p Mod q, if p is less than q
(which is always the case in Top Secret Crypto). We calculate Inverse u such
that (p*u) Mod q = 1.
Next Modulus n is calculated. It is used in both your Public and Secret
Keys. Modulus n = p*q.
The RSA Keys are now complete and are tested. An actual encryption and
decryption test is performed. Some non prime numbers can pass the Fermat
Test causing this test to fail, which is why we do it. When this happens,
you will be asked to generate another set of RSA Keys to test.
Under The Hood: The Math Behind Public and Secret Keys
Top Secret Crypto extracts random bits from the random bits bin to seed
Primes p and q with starting values. A fast sieve method is used to weed out
most of the numbers that are not prime. Those that pass the fast sieve are
tested with Fermat's Theorem to see if it is a possible prime number. I say
possible, because some non prime numbers can pass the Fermat Test. These are
weeded out when the RSA Keys are tested. A prime candidate must pass 4
Fermat Tests to be considered almost 100% prime.
The Fermat Test applies Fermat's Theorem to prime candidate p: For any small
x, if (x(p-1)) Mod p is not equal to 1, then p is not prime. (Remember: Mod
means remainder.)
Once Primes p and q are found, the program calculates the rest of the
numbers needed in forming your Public and Secret Keys.
Phi(n) = (p-1)*(q-1)
G(n) = gcd(p-1, q-1) (gcd: greatest common divisor)
F(n)= Phi(n)/G(n) F(n) = lcm or least common multiple of p-1 and q-1.
Next Exponent e is calculated. This is used in your Public Key to encrypt
with. We always start with a small fixed odd value for e of 17. We look for
an e such that gcd (e, Phi(n)) = 1. If 17 does not work, we then add two to
e and try again. Most of the time 17 does work, and that is why Exponent e
for almost all public keys is 17, or 11 hexadecimal. This small value for
Exponent e makes for very fast encryption no matter what size Modulus n is.
Next Exponent d is calculated. This is used in your Secret Key to decrypt
with. Exponent d is the multiplicative inverse of e Mod F(n). We compute
Exponent d such that (e*d) Mod F(n) = 1.
Next Inverse u is calculated. This value is also used in your Secret Key.
Inverse u is the multiplicative inverse of p Mod q, if p is less than q
(which is always the case in Top Secret Crypto). We calculate Inverse u such
that (p*u) Mod q = 1.
Next Modulus n is calculated. It is used in both your Public and Secret
Keys. Modulus n = p*q.
The RSA Keys are now complete and are tested. An actual encryption and
decryption test is performed. Some non prime numbers can pass the Fermat
Test causing this test to fail, which is why we do it. When this happens,
you will be asked to generate another set of RSA Keys to test.
> Andreas Plesner Jacobsen | The bug stops here.
Håber det oplyste som er fra Brugervejledningen kan bruges.
Lene.