看了里面的内容,好像没有发现有关文档加密解密方面的说明啊。
最近在做一个有关这方面的软件,office文档中的word和excel都提供函数在后台打开带有密码的word和excel文档,access的密码恢复也已经公开了,而powerpoint却没有类似的函数。微软公布的office二进制文档格式也没有加密解密这方面的说明,哪位朋友对这方面有了解吗?
1、怎样通过函数或者其它方式在后台打开带有密码的powerpoint文档;
2、能够快速恢复office文档密码的方法。

  • 标 题:答复
  • 作 者:jeffcjh
  • 时 间:2008-09-05 22:53

微软的office系统文档格式远没有PDF格式透明,加密解密方面的功能就更不用说了,主要是它提供的加密算法存在漏洞,我猜微软不方便公布。

  • 标 题:答复
  • 作 者:jeffcjh
  • 时 间:2008-09-06 10:05

我在因特网上发现过至少三个网站提供在线破译服务,不知你是否知道有更多的?
而离线破译的软件一般是采用黑客字典或暴力穷举方式来求解口令。

这两种情况都需要知道office系统软件的加密机制。实际上其加密机制存在缺陷,前者就是利用这个缺陷实现快速破译的,它并不求出用户口令,而是算出中间过程的密钥来解密doc/xls文件。

后者暴力破解方式就是根据加密机制编写程序来穷举口令的,自然比“采用常规的尝试传密码参数打开office文档来判断密码是否正确的方式”要快得多,但是对于复杂口令基本上也是没戏的。

  • 标 题:答复
  • 作 者:jeffcjh
  • 时 间:2008-09-08 09:15

xiaoxinxx,不知你提出的这个论题是学习兴趣,还是与具体工作有关。

你所说的“OFFICE密码破解软件通过联网瞬间破解密码”,我知道的有三个网站,即
www.rixler.com、www.lastbit.com、www.decryptum.com。
它们提供了各自的客户端供用户提交密报上传给网站服务器进行破解。如果在破解过程中
抓包嗅探,可以大致了解其过程,不过双向的通信数据是加了密的,所以一般是看不出里面
到底是啥东东。

所以我说只有熟悉OFFICE系统软件的加密机制才能深入下去,这样深究下去就复杂了。
由于工作关系暂不能透露细节,如果确有需要,可以进一步联系。

  • 标 题:答复
  • 作 者:jeffcjh
  • 时 间:2008-09-08 19:51

其实关于联网破解office密报的信息,看雪上有篇旧帖子,值得一看,URL为
http://bbs.pediy.com/showthread.php?p=369640&highlight=word#post369640

我相信以此为基础进行研究,可以得到你需要的东西。
(wvware的源代码也值得研读)

  • 标 题:答复
  • 作 者:xiaoxinxx
  • 时 间:2008-09-12 22:06

谢谢jeffcjh和lzype,根据两位高手的解释,基本理解了。现在市面上的密码破解软件就是两种方法:
1、在本机上解密,直接猜测用户口令,这种方法如果是一个弱口令,就可以很快猜出,但是如果是一个强口令的话,比如7、8位以上,这种方法就要花费很长的时间了;
2、直接猜测决定RC4初始化向量的那40位数,这个方法就是需要在线破解,利用服务器的计算资源了。这种方法是获取不到用户的口令的。其实如果是强口令的话,第一种方法获取的口令也不一定就是原口令。


根据lzype说的:
由此提出破解方法1:穷尽5字节s,(4)中的AB可用于验证,只要知道这5字节即可解密文档。(直接穷尽约需10天! )
改进方法2:建立数据库直接查表。
由方法2提出2个问题:
1.必须找到一段固定的5字节或全0处,由这5字节得到RC4的乱数才能查表。
2.数据库如何建立

比较好的应该是建立数据库查表吧。如果是把所有的可能性的数据都存放到数据库中,估计是非常不现实的,那么该怎样合理的建立这个数据库呢?还有,不太理解“必须找到一段固定的5字节或全0处”这句话的意思。

  • 标 题:答复
  • 作 者:jeffcjh
  • 时 间:2008-09-12 23:03

根据我的理解,lzype所说的建立数据库直接查表的实现方法可以有两个:
1、建立全查表:计算保存密码函数的40比特密钥输入与若干字节输出的对应关系,这样需要
   2^40量级的外部存储空间(TB量级),能够保证100%破译;
2、使用彩虹链时空折衷技术,保存部分函数关系,这样大致需要几十G的外存空间,但不保证
   100%的破译
“必须找到一段固定的5字节或全0处”的用意在于建立密码函数的40比特密钥输入与若干字节输出的对应关系。

  • 标 题:答复
  • 作 者:xiaoxinxx
  • 时 间:2008-09-13 10:40

明白了。“必须找到一段固定的5字节或全0处”这句话的意思应该是在makekey生成密钥过程中需要一个64字节的数,而之前传入进来的是一个40位的数(5字节),所以要进行固定的填充(全0:填入59个字节的0)。

  • 标 题:答复
  • 作 者:xiaoxinxx
  • 时 间:2008-09-13 15:42

还有,对于“彩虹链时空折衷技术”也不了解,网上关于彩虹链时空折衷技术的说明也寥寥无几,只找到到一篇文章:瑞士洛桑高级技术大学密码与信息安全实验室的Philippe Oechslin在Crypto2003会议论文集上发表的"Making a Faster CryptanalyticTime-memory Trade-Off(密码分析中一种更快的时空折衷法,http: //lasecwww.epfl.ch/pub/lasec/doc/oech03.pdf)"一文近来在信息安全领域颇受关注.该文声称通过将 D.E.Hellman二十多年前提出的时空折衷攻击法进行了改进,采用了一种被称为彩虹链(RainbowChains)的预计算方法,可以将破解由字母数字构成的MS Windows口令字的时间缩短为在PC机上只有十几秒钟.  

其中http: //lasecwww.epfl.ch/pub/lasec/doc/oech03.pdf链接已经失效了。搜索其它的关键字也没有找到。
jeffcjh能不能详细说说什么叫“彩虹链时空折衷技术”?或者给个链接?

  • 标 题:答复
  • 作 者:jeffcjh
  • 时 间:2008-09-13 19:16

关于彩虹链时空折衷在密码破解上的运用,目前最经典的文件就是oech03.pdf一文,其他都是在此基础上发展出来的一些改进,所以仔细读读这一篇文章足矣。我也是今年初看了看,再结合彩虹链破解的源代码进行了一点研究。给你两个连接,前者为文章,后者为源代码:
http://lasecwww.epfl.ch/~oechslin/publications/crypto03.pdf
http://www.antsight.com/zsl/rainbowcrack/

如果想搞清楚rainbow crack,研读文章和源代码均要做的,我感觉。

  • 标 题:答复
  • 作 者:jeffcjh
  • 时 间:2008-09-13 19:21

不论是全查表还是彩虹表,前提都是建立起一个密码函数,其输入为40比特密钥,输出是RC4算法产生的密钥流(即lzype所说的乱数),所以需要把word加密机制那个地方的细节理解得很清楚,应该说lzype在他的帖子里面就此问题说得比较到位了。

  • 标 题:答复
  • 作 者:jeffcjh
  • 时 间:2008-09-14 10:45

xiaoxinxx,关于的疑问,可以这样解释:
1、我们需要建立的函数关系,其输入只能有40bit密钥,不能包括128bit随机值,否则如你
   猜测,输入空间(即所需存储空间)就会达到2^(40+128)这个天文数了;
2、如何保证函数的输入只有40bit呢?这个就是lzype所说的“必须在word文件中找到一段
   固定的5字节或全0处”的真正含义了。有1个40bit密钥,根据RC4算法,就可以产生出相应
   的密钥流(乱数),如果能做到这样,那么就可以事先建立起2^40个对应关系,记为T 表;
3、现在问题转化成:从word密文中寻找某个底码固定的地方(5字节以上即可),根据
       乱数 = 密文 xor 底码
   的数学公式,可以立即得到乱数(输出),再根据T 表反向查表,即可快速得到40比特密钥
  (输入),有了密钥即可对密报进行立即解密;
4、由此可以看出,那个随机值与随机值的hash其实只是用来验证求出来的密钥的正确性,它们
   本身不可能用来快速破解,快速破解的关键是从word报文中确定底码固定的地方直接拿到
   乱数条件。
Do you understand now ?

  • 标 题:答复
  • 作 者:xiaoxinxx
  • 时 间:2008-09-14 11:58

1、2、4 已经明白了。
3 还有点不明白。主要是不明白
乱数 = 密文 xor 底码
这个数学公式是怎样得出的以及公式里各成员的含义。

  • 标 题:答复
  • 作 者:jeffcjh
  • 时 间:2008-09-14 16:28

“乱数 = 密文 xor 底码”公式中:
密文--就是Word文件中加密后的数据;
底码--就是Word文件中加密之前的数据;
密文和底码按照字节异或(安全人员熟称模二加),就得到乱数了。

由于Word文件格式是OLE复合结构,很容易找到在固定位置上底码固定为0x00的条件,这时
密文就直接等于乱数了。

  • 标 题:答复
  • 作 者:xiaoxinxx
  • 时 间:2008-10-16 16:01

Word解密我已经能够实现暴力破解了。而excel虽然知道加密原理与word一样,但是没有相关的资料,比如密钥、新鲜数等加密后存放的位置。

  • 标 题:答复
  • 作 者:jeffcjh
  • 时 间:2008-10-16 21:13

你新建一个Excel文件后,随便用一个口令加密对它进行加密,保存后用UltraEdit等十六进制工具打开,从文件偏移0x200开始(精确地说是偏移0x214开始),有一个0x002F类型的记录(按小尾序显示为“2F 00”),按照微软EXCEL文件格式说明,它就是专门保存3个随机数的记录,三个随机数(共48字节)从“2F 00 36 00 01 00 01 00 01 00”之后开始。你用它们即可生成解密密钥,具体生成方法与Word完全一样。

  • 标 题:答复
  • 作 者:xiaoxinxx
  • 时 间:2008-10-17 09:29

谢谢jeffcjh,三个数找到了。word和excel的加密方法居然是一样的。

  • 标 题:答复
  • 作 者:jeffcjh
  • 时 间:2008-10-23 21:09

1、powerpoint的加密机制不同于Word,所以需要事先求出PPT的加密算法才能编程穷举口令。
   如何求出PPT的加密算法呢?我觉得只有通过软件反汇编才能做到,我尚未见到对于PPT加密算法的描述,但与word/Excel的默认加密算法肯定是不一样的。

2、“怎样生成查询word和excel的这个全查表?”这个问题我不是太明白你的具体意思,你重新解释一下,好吗?

  • 标 题:答复
  • 作 者:xiaoxinxx
  • 时 间:2008-10-29 21:46

哦,明白了。谢谢。

那么对照表的生成是不是这样。

//这是rc4加密算法
void rc4(unsigned char *buffer_ptr, int buffer_len, rc4_key *key)
{
  unsigned char t;
  unsigned char x;
  unsigned char y;
  unsigned char* state;
  unsigned char xorIndex;
  short counter;

  x = key->x;
  y = key->y;
  state = &key->state[0];
  for(counter = 0; counter < buffer_len; counter++)
  {
    x = (x + 1) % 256;
    y = (state[x] + y) % 256;
    swap_byte(&state[x], &state[y]);
    xorIndex = (state[x] + state[y]) % 256;
    buffer_ptr[counter] ^= state[xorIndex];
  }
  key->x = x;
  key->y = y;
}

其中:
buffer_ptr:从服务器传回本地有40比特的密钥(范围是0x00 0x00 0x00 0x00 0x00-0xff 0xff 0xff 0xff 0xff)
key:从本地传给网站的数据中有5个字节(40比特)
buffer_len:值总是5

然后做一个2^40个循环(输入buffer_ptr,根据buffer_len来生成key)生成rc4的密钥。是这样吗?

  • 标 题:答复
  • 作 者:jeffcjh
  • 时 间:2008-10-30 21:36

To xiaoxinxx:
我认为你提供的rc4算法不完整,缺少了一个阶段。
如果你没意见的话,我可以简单表述一下rc4,并提供我在多个课题中使用过的rc4算法(肯定运算正确)。

如果学术化一点来说的话,rc4加密过程分为两个阶段,第一阶段是密钥调度阶段,将n字节的密钥搅乱成256字节的状态表(最典型的情况是这样);第二阶段是伪随机数(亦称密钥流)生产阶段,即以256字节的状态表为基础,不断交换输出1字节伪随机数(直至满足加密长度的需要)。

  • 标 题:答复
  • 作 者:jeffcjh
  • 时 间:2008-10-30 21:37

我改造的rc4算法供参考:

/* rc4.h */
/*
   This source code of RC4 algorithm is rewritten by Jeff Chen.
*/

#ifndef HEADER_RC4_H
#define HEADER_RC4_H

#ifdef  __cplusplus
extern "C" {
#endif


typedef unsigned int UINT4;
typedef unsigned char UCHAR;

/* internal structure used by RC4_KSA & RC4_PRGA */
typedef struct rc4_state
{
  UCHAR S[256];
  UCHAR i;
  UCHAR j;
} RC4_STATE;

void  RC4_KSA(UCHAR *rc4key, int KL, RC4_STATE *state);
void  RC4_KSA_128(UCHAR *rc4key, RC4_STATE *state);
UCHAR RC4_PRGA(RC4_STATE *state);
void  RC4(UCHAR *rc4key, int keylen, UCHAR *keystream, int kslen);


#ifdef  __cplusplus
}
#endif

#endif /* HEADER_RC4_H */

  • 标 题:答复
  • 作 者:jeffcjh
  • 时 间:2008-10-30 21:37

/* rc4.c */
/*
 *  This source code of RC4 algorithm is rewritten by Jeff Chen.
 */

#include "rc4.h"

/*
 * This source code of RC4 algorithm is rewritten by Jeff Chen.
 */

/* 密钥长度为KL字节 */
void RC4_KSA(UCHAR *rc4key, int KL, RC4_STATE *state)
{
  /*
   * 注意: i不能定义为UCHAR, 否则
   * for (i = 0; i < 256; i++)是死循环 
   */
  int i;
  UCHAR j, tmp;
  UCHAR *s = state->S;
  
  /* Initialization */
  state->i = 0;  state->j = 0;
  for (i = 0; i < 256; i++)  s[i] = i;

  /* Scrambling */
  j = 0;
  for (i = 0; i < 256; i++)
  {
    j += s[i] + rc4key[i % KL];  // 自动丢弃j的高字节部分
    tmp = s[i];  s[i] = s[j];  s[j] = tmp;
  }
}

/* 密钥长度固定为16字节 */
void RC4_KSA_128(UCHAR *rc4key, RC4_STATE *state)
{
  /*
   * 注意: i不能定义为UCHAR, 否则
   * for (i = 0; i < 256; i++)是死循环 
   */
  int i;
  UCHAR j, tmp;
  UCHAR *s = state->S;
  
  /* Initialization */
  state->i = 0;  state->j = 0;
  for (i = 0; i < 256; i++)  s[i] = i;

  /* Scrambling */
  j = 0;
  for (i = 0; i < 256; i++)
  {
    j += s[i] + rc4key[i & 0x0f];  // 自动丢弃j的高字节部分
    tmp = s[i];  s[i] = s[j];  s[j] = tmp;
  }
}

/* output one byte of keystream */
UCHAR RC4_PRGA(RC4_STATE *state)
{
  UCHAR *s, *i, *j, tmp;

  s = state->S;
  i = &(state->i);
  j = &(state->j);

  ++*i;
  *j += s[*i];

  tmp = s[*i];  s[*i] = s[*j];  s[*j] = tmp;

  return s[(s[*i] + s[*j]) & 0xff];  // 注意: 必须加上 "& 0xff"
}

/* 
   Combine the two stage of rc4 algorithm.
   output kslen bytes of keystream.
   here keylen is the byte length of rc4 key.
*/
void RC4(UCHAR *rc4key, int keylen, UCHAR *keystream, int kslen)
{
  int n;
  RC4_STATE state;

  if (keylen == 16)  RC4_KSA_128(rc4key, &state);
  else            RC4_KSA(rc4key, keylen, &state);
  
  for (n = 0; n < kslen; n++)
    keystream[n] = RC4_PRGA(&state);
}

  • 标 题:答复
  • 作 者:jeffcjh
  • 时 间:2008-10-30 21:55

现在再来回答你的问题。

word加密。你已基本知道Word的加密过程。给定40比特(5字节)密钥 key 后,经由md5得到128字节的rc4密钥,再通过rc4加密算法(注:包括两个阶段)生产出5字节的伪随机数 ks (密钥流)。

这样就定义出了一个函数关系f,即 5字节key(输入)  映射到  5字节ks(输出)。
按照全查表方式,如果我们事先计算好全部(2^40)个输入的输出结果,这样知道5字节的伪随机数(f的输出),只需一个查表操作就可知f的输入,计算时间为O(1)。

但是全查表方式需要O(2^40)的外存空间,有点大了。所以有人想出了彩虹链时空折衷方式,大大降低了存储空间,但是也增加了计算时间(不过相较于O(2^40)量级,还是要快得多)。这里你读过相关文章,应该了解了。

这样一来,要想快速破解Word密报,问题就归结为如何得到比如5字节的 f 函数的输出,所以进一步追问到Word密报中的固定底码,由它可以立即得到 f 函数的部分输出,通过全查表或者彩虹链查表即可快速得到 f 函数的输入,即5字节密钥。 有了5字节密钥,解密即可瞬间完成。

不知我说清楚了没有?

  • 标 题:答复
  • 作 者:jeffcjh
  • 时 间:2008-10-30 22:00

word固定底码的位置问题,只需自己用UE或WinHEX之类的观察几个Word文件就可定出来,不存在啥问题。

那几个网站使用的固定位置在哪里呢?这个需要你去动手调试他们提供的客户端软件,容易搞清楚,我这里就不说了。

  • 标 题:答复
  • 作 者:xiaoxinxx
  • 时 间:2008-10-31 15:16

"给定40比特(5字节)密钥 key 后,经由md5得到128字节的rc4密钥,再通过rc4加密算法(注:包括两个阶段)生产出5字节的伪随机数 ks (密钥流)。这样就定义出了一个函数关系f,即 5字节key(输入)  映射到  5字节ks(输出)。"

这样的话,5字节key(输入)映射到5字节ks(输出)会不会有碰撞?如果有碰撞的话,怎样解决呢?

  • 标 题:答复
  • 作 者:jeffcjh
  • 时 间:2008-10-31 20:29

提得有道理! 

的确可能发生碰撞,因为这个函数一般并不是一一映射(双射),所以根据某个输出来查表可能会得到若干个输入。此时如果区分呢?当然有办法,因为Word/Excel中本身就设置了密钥验证条件。还记得那3个16字节的随机数吗?快速破译到目前为止,它们还没有派上用场呢,自然有其用处,即用求得的输入(5字节)派生出rc4密钥来解密第2个16字节和第3个16字节,再对解密结果进行判断,若md5(第2个16字节) == md5(第3个16字节)成立,则该输入正确,否则尝试其他输入。这就是区分方法。

上述分析涉及到的具体细节可以参考最早给你阅读的看雪帖子,里面对3个16字节随机数的作用说得非常清楚了。

  • 标 题:答复
  • 作 者:xiaoxinxx
  • 时 间:2008-10-31 21:20

1、意思是说全查表中的5字节key(输入)A映射到5字节ks(输出)B的关系中,B发生碰撞是正常的,可以返回多个A值给客户端,然后客户端先验证A 值是否正确,如果正确则解密文件内容。是这样吗?
2、A值的范围是不是从0X00 0X00 0X00 0X00 0X00--0XFF 0XFF 0XFF 0XFF 0XFF,循环这个范围的A值,然后产生5字节ks(输出)B的全查表?
3、由于全查表有2^40条记录,大概是1兆条,如果全部放到某个文件或者放到数据库中都不合适,所以我想采用下面这种方法:
   a、把这1兆条记录按照5字节ks(输出)B的区间范围分别存放到100万个文件中(此文件为txt文件压缩成rar文件,如果不压缩,那么1兆条记录所占用的磁盘空间大概是10T左右,压缩后占用的磁盘空间缩小为原来的近1/40);
   b、把这100万个文件的信息(包括文路径和文件名,以及文件中100万条记录的5字节ks(输出)B的区间范围等信息)都存放到数据库某个表中(称为C表);
   c、服务器接收客户端传递回来的5字节ks(输出)B,就查询C表,然后确认此5字节ks(输出)B对应的A所在的文件名和路径(如果做好了B数据的索引,那么查询速度应该是很快的,大概在1秒左右就可以查询出);
   d、有了路径和文件名,直接解压并打开此文件,查询此文件中的100万条记录(时间大概是几秒)。
    由于我需要的是首先考虑查询速度,其次才是占用的磁盘空间,所以采用此方法,而不采用彩虹链时空折衷方式,此方法有个不好的地方,就是前期要做大量的准备工作,比如对1兆条记录中的5字节ks(输出)B进行排序等。对于此方法,您能不能给点建议和意见?或者有没有其它更加好的方法。再次感谢!

  • 标 题:答复
  • 作 者:jeffcjh
  • 时 间:2008-11-01 00:38

1、区分碰撞的工作是网站服务器来做的,所以客户端在提交Doc文件时,会将48字节的随机数发给服务器;
2、f函数的输入(A值)的范围是从0X00 0X00 0X00 0X00 0X00--0XFF 0XFF 0XFF 0XFF 0XFF;
3、记录数2^40不是1兆,而是1024G(即1T)。关于具体实施方法,你已经提出来了,大概差不多,我的意见是:

1)按照(f的输出)B将输入A分类,若存放到100万(2^20)个文件中,那每个文件存有2^20条记录。文件个数是否太多了? 我建议存放到2^16个文件中,每个文件存有2^24条记录比较合适。而每个文件不需以TXT方式保存数据,而是5字节5字节的写入。如果想节省空间,我倒认为可以将文件中的2^24个5字节作一下差分(即相临5字节相减),这样5字节减差的最高2字节绝大多数是0x00(原因你自己思考),不需保存,只需保存3字节;遇到极少数最高2字节不为0x00的,特别处理一下。综合考虑,可以自己设计一个数据结构来保存每个文件的差分序列,使解密时可以还原成原序列,应该不困难;

2)后面你提到的查询计算没啥问题。的确,前期是要做大量的准备工作,但这种工作只做一次,以后就再也不需要了,还是划得来的。

  • 标 题:答复
  • 作 者:xiaoxinxx
  • 时 间:2008-11-01 10:31

1、2^40算出的结果是1099511627776,也就是大概1兆条记录啊。
2、“我建议存放到2^16个文件中,每个文件存有2^24条记录比较合适”-- 好的。
3、“而每个文件不需以TXT方式保存数据,而是5字节5字节的写入”--意思是没有文件类型,而只是有文件名?这样有什么好处呢?而5字节5字节的写入,是不是这种方式:
    A                          B
      000102030405    050403020100
      A1B2C3D4E5F6    F6E5D4C3B2A1
      ......
      ......    
4、“如果想节省空间,我倒认为可以将文件中的2^24个5字节作一下差分(即相临5字节相减),这样5字节减差的最高2字节绝大多数是0x00(原因你自己思考),不需保存,只需保存3字节;遇到极少数最高2字节不为0x00的,特别处理一下。”--文件还有没有压缩的必要呢?因为如果压缩的话,所占用的磁盘空间大大缩小了,而如果机器性能好的话,查询速度应该不会有多大的影响吧。
5、由于要对2^40条记录的字节ks(输出)B进行排序,所以事先要做好准备工作,这个准备工作有两种方法:
  a、在完成全查表的生成之后再做进行排序;这样做的好处就是生成全查表的速度快,但是后面的工作就很麻烦了;
  b、在生成全查表的过程中就开始做。比如事先约定好某条记录按照字节ks(输出)B的区间范围来确定它所属的文件,生成这条记录时就插入到所属的文件中。这种方法生成全查表的速度慢,但是一旦生成完,那么排序的工作就几乎完成了。
  我打算选择第二中方法,您的建议呢?或者有没有其它更好的方法?

  • 标 题:答复
  • 作 者:jeffcjh
  • 时 间:2008-11-01 11:45

1、通常所说的1兆是指2^20,你是否理解有误?
2、文件名信息不需要存入那2^16个纯数据文件中。每个这样的文件平均保存2^24个记录,这里的所谓记录其实就是(f函数的)输入A,每个都是5字节,所以我说是5字节5字节的写入,当然最后可以对每个文件中的2^24个A进行升序排列。  注意:这个文件中的2^24个A(f的输入)对应的是同一个输出B,所以我们将它们纠集在一个文件中,这样根据B查表的时候,只需在这个文件中进行遍历即可;
3、你所说的对每个文件进行压缩是可以的,具体要看压缩率。我所说的对每个文件的2^24个A(升序排列后)进行差分得到差分序列,序列中的每一项(除第1项外,因为它是原始的)基本上最高三个字节都为0x00(前面说的最高2字节为0x00,有点小错误),这样就只需保存低2字节了。
4、按照前面我说的思路,就不存在“事先就要对2^40个ks(输出)B进行快速排序”这个问题了,因为对2^40条记录已经被摊分到2^16个文件中去了,只需对每个文件中的2^24个A进行排序。当然这个计算有点花时间,不知你能否做得起,一般是要在集群机上才能完成的,单机跑的话时间有点长。

  • 标 题:答复
  • 作 者:xiaoxinxx
  • 时 间:2008-11-01 12:27

1、哦。是我理解有误了。在没有压缩和其它任何处理的情况下,产生的全查表大概占多大的磁盘空间呢?
2、因为我还没有生成这个全查表,所以不清楚B记录的关系,按照您说的意思,B记录存在大量的碰撞,也就是说,同一个B值,会有2^24个A值(f的输入)的对应?在2^16个文件中,每个文件中的只需要存放A值就够了,因为这些A值所对应的B值都是一样的?如果这样的话,不会存在根据客户端传回的B值而查询不到A值的情况吧。
3、OK。
4、这样说的话,前期的主要准备工作就不是对B值进行排序,而是把相同的B值划分到同一个文件中了(有什么效率比较高的方法吗)?那么查询速度的瓶颈就在于查询这个有2^24个A的文件上了?

谢谢jeffcjh!如果没有您的帮助,估计我会走很多很多的弯路。而现在节约了非常多的时间!太感谢了!